跳转至

分塊思想

簡介

其實，分塊是一種思想，而不是一種數據結構。

從 NOIP 到 NOI 到 IOI，各種難度的分塊思想都有出現。

分塊的基本思想是，通過對原數據的適當劃分，並在劃分後的每一個塊上預處理部分信息，從而較一般的暴力算法取得更優的時間複雜度。

分塊的時間複雜度主要取決於分塊的塊長，一般可以通過均值不等式求出某個問題下的最優塊長，以及相應的時間複雜度。

分塊是一種很靈活的思想，相較於樹狀數組和線段樹，分塊的優點是通用性更好，可以維護很多樹狀數組和線段樹無法維護的信息。

當然，分塊的缺點是漸進意義的複雜度，相較於線段樹和樹狀數組不夠好。

不過在大多數問題上，分塊仍然是解決這些問題的一個不錯選擇。

下面是幾個例子。

區間和

例題 LibreOJ 6280 數列分塊入門 4

給定一個長度為 \(n\) 的序列 \(\{a_i\}\)，需要執行 \(n\) 次操作。操作分為兩種：

  1. 給 \(a_l \sim a_r\) 之間的所有數加上 \(x\)；

  2. 求 \(\sum_{i=l}^r a_i\)。

    \(1 \leq n \leq 5 \times 10^4\)

我們將序列按每 \(s\) 個元素一塊進行分塊，並記錄每塊的區間和 \(b_i\)。

\[ \underbrace{a_1, a_2, \ldots, a_s}_{b_1}, \underbrace{a_{s+1}, \ldots, a_{2s}}_{b_2}, \dots, \underbrace{a_{(s-1) \times s+1}, \dots, a_n}_{b_{\frac{n}{s}}} \]

最後一個塊可能是不完整的（因為 \(n\) 很可能不是 \(s\) 的倍數），但是這對於我們的討論來説並沒有太大影響。

首先看查詢操作：

  • 若 \(l\) 和 \(r\) 在同一個塊內，直接暴力求和即可，因為塊長為 \(s\)，因此最壞複雜度為 \(O(s)\)。
  • 若 \(l\) 和 \(r\) 不在同一個塊內，則答案由三部分組成：以 \(l\) 開頭的不完整塊，中間幾個完整塊，以 \(r\) 結尾的不完整塊。對於不完整的塊，仍然採用上面暴力計算的方法，對於完整塊，則直接利用已經求出的 \(b_i\) 求和即可。這種情況下，最壞複雜度為 \(O(\dfrac{n}{s}+s)\)。

接下來是修改操作：

  • 若 \(l\) 和 \(r\) 在同一個塊內，直接暴力修改即可，因為塊長為 \(s\)，因此最壞複雜度為 \(O(s)\)。
  • 若 \(l\) 和 \(r\) 不在同一個塊內，則需要修改三部分：以 \(l\) 開頭的不完整塊，中間幾個完整塊，以 \(r\) 結尾的不完整塊。對於不完整的塊，仍然是暴力修改每個元素的值（別忘了更新區間和 \(b_i\)），對於完整塊，則直接修改 \(b_i\) 即可。這種情況下，最壞複雜度和仍然為 \(O(\dfrac{n}{s}+s)\)。

利用均值不等式可知，當 \(\dfrac{n}{s}=s\)，即 \(s=\sqrt n\) 時，單次操作的時間複雜度最優，為 \(O(\sqrt n)\)。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cmath>
#include <iostream>
using namespace std;
int id[50005], len;
// id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优
long long a[50005], b[50005], s[50005];

// a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s
// 表示块内元素总和
void add(int l, int r, long long x) {  // 区间加法
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // 在一个块中
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++)
    b[i] += x, s[i] += len * x;  // 更新区间和数组(完整的块)
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // 以上两行不完整的块直接简单求和,就OK
}

long long query(int l, int r, long long p) {  // 区间查询
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // 在一个块里直接暴力求和
    for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p;
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p;
  for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p;
  for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p;
  // 和上面的区间修改是一个道理
  return ans;
}

int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // 均值不等式可知复杂度最优为根号n
  for (int i = 1; i <= n; i++) {  // 题面要求
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }
  for (int i = 1; i <= n; i++) {
    int op, l, r, c;
    cin >> op >> l >> r >> c;
    if (op == 0)
      add(l, r, c);
    else
      cout << query(l, r, c + 1) << endl;
  }
  return 0;
}

/*
https://loj.ac/s/1151495
 */

區間和 2

上一個做法的複雜度是 \(\Omega(1) , O(\sqrt{n})\)。

我們在這裏介紹一種 \(O(\sqrt{n}) - O(1)\) 的算法。

為了 \(O(1)\) 詢問，我們可以維護各種前綴和。

然而在有修改的情況下，不方便維護，只能維護單個塊內的前綴和。

以及整塊作為一個單位的前綴和。

每次修改 \(O(T+\frac{n}{T})\)。

詢問：涉及三部分，每部分都可以直接通過前綴和得到，時間複雜度 \(O(1)\)。

對詢問分塊

同樣的問題，現在序列長度為 \(n\)，有 \(m\) 個操作。

如果操作數量比較少，我們可以把操作記下來，在詢問的時候加上這些操作的影響。

假設最多記錄 \(T\) 個操作，則修改 \(O(1)\)，詢問 \(O(T)\)。

\(T\) 個操作之後，重新計算前綴和，\(O(n)\)。

總複雜度：\(O(mT+n\frac{m}{T})\)。

\(T=\sqrt{n}\) 時，總複雜度 \(O(m \sqrt{n})\)。

其他問題

分塊思想也可以應用於其他整數相關問題：尋找零元素的數量、尋找第一個非零元素、計算滿足某個性質的元素個數等等。

還有一些問題可以通過分塊來解決，例如維護一組允許添加或刪除數字的集合，檢查一個數是否屬於這個集合，以及查找第 \(k\) 大的數。要解決這個問題，必須將數字按遞增順序存儲，並分割成多個塊，每個塊中包含 \(\sqrt{n}\) 個數字。每次添加或刪除一個數字時，必須通過在相鄰塊的邊界移動數字來重新分塊。

一種很有名的離線算法 莫隊算法，也是基於分塊思想實現的。

練習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, HeRaNO, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用