分块思想

简介

既然在数据结构单元里面，那么为什么还称为“思想”呢？其实分块严格意义上来说并不是一种数据结构，而是一种思想，不过这种思想却能引申出很多的数据结构和算法。

分块的难度跳跃非常大，简单到普及组，难道 IOI，到处都有，因此我们现在就来学习它的思想吧。

例题

区间求和

给定长度为 \(n\) 的序列和 \(m\) 个询问，每一个询问都是将一个区间内的值都加上给定的数，或是求出给定区间的和。要求在 \(\mathcal O(m\sqrt{n})\) 的复杂度之内实现。

由于暴力的时间复杂度为 \(\mathcal O(nm)\)，因此我们需要想一个更优的方法。我们把整个序列分成 \(l\) 块，每一块长 \(\cfrac{n}{l}\)，接下来就好办了，因为每一段修改或询问的区间都能分成一下三份：

• 在前面的一部分零散的元素；
• 中间的若干个整块；
• 后面的一部分零散的元素。

照样子模拟操作就行了。注意如果是修改整块的话，我们其实只是在块的属性里面加上了修改的值，实际的内容是没有变的，而以后当修改到这一部分林零散的内容时，就会出错。因此我们可以添加一个标记数组，表示每一个块加上了多少的值，然后统计答案的时候加上就行了。

最后我们发现，询问和修改的时间复杂度都是 \(\mathcal O(n+\dfrac{n}{l})\) 的，那么我们需要将这个值最小化。很显然，当 \(l=\sqrt{n}\) 的时候，也就是 \(l=\dfrac{n}{l}\) 的时候，时间复杂度是最优的。

代码

#include <iostream>
#include <cmath>

using namespace std;
using int64 = long long;

const int64 kMaxN = 1e5 + 5;

int64 a[kMaxN], tag[kMaxN], id[kMaxN], sum[kMaxN], n, m, len;

void update(int64 l, int64 r, int64 k) {
  int64 x = id[l], y = id[r];
  if (x == y) {
    for (int64 i = l; i <= r; i++) {
      a[i] += k, sum[x] += k;
    }
    return;
  }
  for (int64 i = l; id[i] == x; i++) {
    a[i] += k, sum[x] += k;
  }
  for (int64 i = x + 1; i < y; i++) {
    tag[i] += k, sum[i] += len * k;
  }
  for (int64 i = r; id[i] == y; i--) {
    a[i] += k, sum[y] += k;
  }
}

int64 query(int64 l, int64 r) {
  int64 x = id[l], y = id[r], ans = 0;
  if (x == y) {
    for (int64 i = l; i <= r; i++) {
      ans += a[i] + tag[x];
    }
    return ans;
  }
  for (int64 i = l; id[i] == x; i++) {
    ans += a[i] + tag[x];
  }
  for (int64 i = x + 1; i < y; i++) {
    ans += sum[i];
  }
  for (int64 i = r; id[i] == y; i--) {
    ans += a[i] + tag[y];
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  len = sqrt(n);
  for (int64 i = 1; i <= n; i++) {
    cin >> a[i];
    sum[id[i] = (i - 1) / len + 1] += a[i];
  }
  for (int64 o, x, y, k; m; m--) {
    cin >> o >> x >> y;
    if (o == 1) {
      cin >> k;
      update(x, y, k);
    } else {
      cout << query(x, y) << '\n';
    }
  }
  return 0;
}

后记

分块虽然只是一种思想，但是能够解决很多的实际问题。例如，一种很有名的离线算法——莫队算法，就是基于分块实现的。

评论