跳转至

# 分块思想

## 简介

其实，分块是一种思想，而不是一种数据结构．

从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现．

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度．

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度．

分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息．

当然，分块的缺点是渐近意义的复杂度，相较于线段树和树状数组不够好．

不过在大多数问题上，分块仍然是解决这些问题的一个不错选择．

下面是几个例子．

## 区间和

例题 LibreOJ 6280 数列分块入门 4

给定一个长度为 𝑛 n 的序列 {𝑎 𝑖}{a i}，需要执行 𝑛 n 次操作．操作分为两种：

1. 给 𝑎 𝑙 ∼𝑎 𝑟 a l∼a r 之间的所有数加上 𝑥 x；

2. 求 ∑𝑟 𝑖=𝑙 𝑎 𝑖∑i=l r a i．

   1 ≤𝑛 ≤5 ×1 0 4 1≤n≤5×10 4

我们将序列按每 𝑠 s 个元素一块进行分块，并记录每块的区间和 𝑏 𝑖 b i．

𝑎 1,𝑎 2,…,𝑎 𝑠⏟__⏟__⏟𝑏 1,𝑎 𝑠+1,…,𝑎 2 𝑠⏟__⏟__⏟𝑏 2,…,𝑎(𝑠−1)×𝑠+1,…,𝑎 𝑛⏟___⏟___⏟𝑏 𝑛 𝑠 a 1,a 2,…,a s⏟b 1,a s+1,…,a 2 s⏟b 2,…,a(s−1)×s+1,…,a n⏟b n s

最后一个块可能是不完整的（因为 𝑛 n 很可能不是 𝑠 s 的倍数），但是这对于我们的讨论来说并没有太大影响．

首先看查询操作：

- 若 𝑙 l 和 𝑟 r 在同一个块内，直接暴力求和即可，因为块长为 𝑠 s，因此最坏复杂度为 𝑂(𝑠)O(s)．
- 若 𝑙 l 和 𝑟 r 不在同一个块内，则答案由三部分组成：以 𝑙 l 开头的不完整块，中间几个完整块，以 𝑟 r 结尾的不完整块．对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 𝑏 𝑖 b i 求和即可．这种情况下，最坏复杂度为 𝑂(𝑛 𝑠 +𝑠)O(n s+s)．

接下来是修改操作：

- 若 𝑙 l 和 𝑟 r 在同一个块内，直接暴力修改即可，因为块长为 𝑠 s，因此最坏复杂度为 𝑂(𝑠)O(s)．
- 若 𝑙 l 和 𝑟 r 不在同一个块内，则需要修改三部分：以 𝑙 l 开头的不完整块，中间几个完整块，以 𝑟 r 结尾的不完整块．对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 𝑏 𝑖 b i），对于完整块，则直接修改 𝑏 𝑖 b i 即可．这种情况下，最坏复杂度和仍然为 𝑂(𝑛 𝑠 +𝑠)O(n s+s)．

利用均值不等式可知，当 𝑛 𝑠 =𝑠 n s=s，即 𝑠 =√𝑛 s=n 时，单次操作的时间复杂度最优，为 𝑂(√𝑛)O(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

上一个做法的复杂度是 Ω(1),𝑂(√𝑛)Ω(1),O(n)．

我们在这里介绍一种 𝑂(√𝑛) −𝑂(1)O(n)−O(1) 的算法．

为了 𝑂(1)O(1) 询问，我们可以维护各种前缀和．

然而在有修改的情况下，不方便维护，只能维护单个块内的前缀和．

以及整块作为一个单位的前缀和．

每次修改 𝑂(𝑇 +𝑛 𝑇)O(T+n T)．

询问：涉及三部分，每部分都可以直接通过前缀和得到，时间复杂度 𝑂(1)O(1)．

## 对询问分块

同样的问题，现在序列长度为 𝑛 n，有 𝑚 m 个操作．

如果操作数量比较少，我们可以把操作记下来，在询问的时候加上这些操作的影响．

假设最多记录 𝑇 T 个操作，则修改 𝑂(1)O(1)，询问 𝑂(𝑇)O(T)．

𝑇 T 个操作之后，重新计算前缀和，𝑂(𝑛)O(n)．

总复杂度：𝑂(𝑚 𝑇 +𝑛 𝑚 𝑇)O(m T+n m T)．

𝑇 =√𝑛 T=n 时，总复杂度 𝑂(𝑚√𝑛)O(m n)．

### 其他问题

分块思想也可以应用于其他整数相关问题：寻找零元素的数量、寻找第一个非零元素、计算满足某个性质的元素个数等等．

还有一些问题可以通过分块来解决，例如维护一组允许添加或删除数字的集合，检查一个数是否属于这个集合，以及查找第 𝑘 k 大的数．要解决这个问题，必须将数字按递增顺序存储，并分割成多个块，每个块中包含 √𝑛 n 个数字．每次添加或删除一个数字时，必须通过在相邻块的边界移动数字来重新分块．

一种很有名的离线算法 莫队算法，也是基于分块思想实现的．

## 练习题

- UVa - 12003 - Array Transformer
- UVa - 11990 Dynamic Inversion
- SPOJ - Give Away
- Codeforces - Till I Collapse
- Codeforces - Destiny
- Codeforces - Holes
- Codeforces - XOR and Favorite Number
- Codeforces - Powerful array

- SPOJ - DQUERY

  本页面主要译自博文 Sqrt-декомпозиция 与其英文翻译版 Sqrt Decomposition．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, StudyingFather, Xeonacid, Yanjun-Zhao, c-forrest, HeRaNO, Chrogeek, Enter-tainer, gi-b716, kenlig, ksyx, linghaiyi, Tiphereth-A, yiyangit
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用