分块

lunivia · 2025-09-16 19:21:32 · 个人记录

引入

分块，一种根号实现。使用它可以轻松完成一些 \log 数据结构需要很久才能完成/实现比较困难的东西，在 n\le 2e5 时候可以考虑尝试使用。

分块基本实现思路是，将块分成 blo 块。对于区间维护信息 [l,r]，实现以下做法：

1. 目前元素所在的块不被完整包含在 [l,r] 内，那么暴力维护。
2. 目前元素所在的块被完整包含在 [l,r] 内，即 a\in [L_x,R_x],[L_x,R_x]\subset [l,r]（其中，L_x,R_x 是块 x 的左右端点），那么则对目前块维护懒标记，就像线段树一样。单个块时间复杂度一般情况下为 \Theta(1)，故时间复杂度为 \Theta(\frac{n}{blo})。

单次修改/查询时间为 2*\Theta(blo)+\Theta(\frac{n}{blo})=\Theta(\frac{n}{blo}+blo)。使用均值不等式： \frac{n}{blo}+blo\ge2\sqrt n，即当 \frac{n}{blo}=blo\rightarrow blo=\sqrt n 时取到最小值。故一般情况下 blo 取 \sqrt n 时间复杂度最优，为 \Theta(q\sqrt n)。

这里使用数列分块的一些题目展示分块的实现和基本的 trick。

基本题

数列分块1

区间加，单点查。

维护两个值 sum,add 分别为每个块的总和和懒标记加。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int _ = 3e5 + 5; 

int n,siz;
int a[_],id[_],add[_];

signed main() {
  cin >> n;
  siz = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
    id[i] = (i - 1) / siz + 1; 
  }
  for(int i = 1,op,l,r,c;i <= n;i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] += c; //注意：特殊情况，在同一个块内则直接暴力加
      } else {
        for(int j = l;id[j] == id[l];j++) a[j] += c; //左边不完整块
        for(int j = r;id[j] == id[r];j--) a[j] += c; //右边不完整块
        for(int j = id[l] + 1;j < id[r];j++) add[j] += c; //中间完整块
      }
    } else {
      cout << a[r] + add[id[r]] << '\n'; //记得加懒标记
    }
  }
  return 0;
}

数列分块4

区间加，区间和。

同线段树，简单维护 sum,add 即可。

注：这里维护了 L_x,R_x，因为 sqrt(n) 是向下取整，所以剩下不够的再单独分一个块。

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int _ = 3e5 + 5; 

int n,blo;
int a[_];
int L[_],R[_],id[_],add[_],sum[_];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
      sum[i] = sum[i] + a[j];
    }
  }
  for(int i = 1,op,l,r,c;i <= n;i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] += c,sum[id[l]] += c;
      } else {
        for(int j = l;j <= R[id[l]];j++) a[j] += c,sum[id[l]] += c;
        for(int j = L[id[r]];j <= r;j++) a[j] += c,sum[id[r]] += c;
        for(int j = id[l] + 1;j < id[r];j++) add[j] += c,sum[j] += c * (R[j] - L[j] + 1);
      }
    } else {
      int ans = 0;
      c++;
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) ans += a[j] + add[id[l]];
      } else {
        for(int j = l;j <= R[id[l]];j++) ans += a[j] + add[id[l]];
        for(int j = L[id[r]];j <= r;j++) ans += a[j] + add[id[r]];
        for(int j = id[l] + 1;j < id[r];j++) ans += sum[j];
      }
      cout << (ans % c + c) % c << '\n'; //最后取模，不然这题会被卡
    }
  }
  return 0;
}

数列分块7

考虑维护两个tag：add 和 mul，想象一下怎么维护。

具体做法：令 mul 优先级大于 add，即先算 mul 再算 add。显然 add 操作时只需要更新 add，而 mul 操作时由于是每个数乘 x，故 add 也要乘 x。

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int _ = 3e5 + 5,Mod = 10007;

int n,blo;
int a[_];
int L[_],R[_],id[_],add[_],mul[_];

void Push(int x) {
  if(mul[id[x]] == 1 && add[id[x]] == 0) return;
  for(int i = L[id[x]];i <= R[id[x]];i++) {
    a[i] = (a[i] * mul[id[x]] % Mod + add[id[x]]) % Mod;
  }
  mul[id[x]] = 1,add[id[x]] = 0;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
    a[i] %= Mod; 
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    mul[i] = 1;
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
    }
  }
  for(int i = 1,op,l,r,c;i <= n;i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      Push(l),Push(r);
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] = (a[j] + c) % Mod;
      } else {
        for(int j = l;j <= R[id[l]];j++) a[j] = (a[j] + c) % Mod;
        for(int j = L[id[r]];j <= r;j++) a[j] = (a[j] + c) % Mod;
        for(int j = id[l] + 1;j < id[r];j++) add[j] = (add[j] + c) % Mod;
      }
    } else if(op == 1) {
      Push(l),Push(r);
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] = a[j] * c % Mod;
      } else {
        for(int j = l;j <= R[id[l]];j++) a[j] = a[j] * c % Mod;
        for(int j = L[id[r]];j <= r;j++) a[j] = a[j] * c % Mod;
        for(int j = id[l] + 1;j < id[r];j++) mul[j] = mul[j] * c % Mod,add[j] = add[j] * c % Mod;
      }
    } else {
      cout << ((a[r] * mul[id[r]] + add[id[r]]) % Mod + Mod) % Mod << '\n'; 
    }
  }
  return 0;
}

一些更好玩的

上述操作用线段树等结构依旧较好操作，分块的优势并未体现出来。接下来的几道题目会让你真正认识到分块的通用性，这些是线段树等 \log 复杂度无法轻易做出的，但分块可以，因为分块本质上是暴力优化。

数列分块2

单点加，区间寻找小于 c^2 的数的个数。

考虑对于每个块维护一个排序版本 b_i，然后左右不完整块暴力查询，中间使用 lower\_bound 或手写二分查询。每次左右的时候都要重新覆盖一次数组。完整块时间复杂度为 \log blo。完整块加法时候不需要排序，因为不会改变原来相对位置。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int _ = 2e5 + 5; 

int n,blo;
int a[_];
int L[_],R[_],id[_],add[_];
vector<int> vec[_];

void Sort(int x) { //用于暴力推平/重构 
  vec[x].clear();
  for(int i = L[x];i <= R[x];i++) vec[x].push_back(a[i]);
  sort(vec[x].begin(),vec[x].end());
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
    }
  }
  for(int i = 1;i <= blo;i++) Sort(i);
  for(int i = 1,op,l,r,c;i <= n;i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] += c;
        Sort(id[l]);
      } else {
        for(int j = l;j <= R[id[l]];j++) a[j] += c;
        for(int j = L[id[r]];j <= r;j++) a[j] += c;
        Sort(id[l]),Sort(id[r]);
        for(int j = id[l] + 1;j < id[r];j++) add[j] += c;
      }
    } else {
      int ans = 0;
      c *= c;
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) ans += (a[j] + add[id[l]] < c);
      } else {
        for(int j = l;j <= R[id[l]];j++) ans += (a[j] + add[id[j]] < c);
        for(int j = L[id[r]];j <= r;j++) ans += (a[j] + add[id[j]] < c);
        for(int j = id[l] + 1;j < id[r];j++) ans += lower_bound(vec[j].begin(),vec[j].end(),c - add[j]) - vec[j].begin(); //二分
      }
      cout << ans << '\n';
    }
  }
  return 0;
}

数列分块3

跟上面大同小异。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int _ = 2e5 + 5; 

int n,blo;
int a[_];
int L[_],R[_],id[_],add[_];
vector<int> vec[_];

void Sort(int x) {
  vec[x].clear();
  for(int i = L[x];i <= R[x];i++) vec[x].push_back(a[i]);
  sort(vec[x].begin(),vec[x].end());
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
    }
  }
  for(int i = 1;i <= blo;i++) Sort(i);
  for(int i = 1,op,l,r,c;i <= n;i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) a[j] += c;
        Sort(id[l]);
      } else {
        for(int j = l;j <= R[id[l]];j++) a[j] += c;
        for(int j = L[id[r]];j <= r;j++) a[j] += c;
        Sort(id[l]),Sort(id[r]);
        for(int j = id[l] + 1;j < id[r];j++) add[j] += c;
      }
    } else {
      int ans = LONG_LONG_MIN; 
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) ans = max(ans,a[j] + add[id[l]] < c ? a[j] + add[id[l]] : LONG_LONG_MIN);
      } else {
        for(int j = l;j <= R[id[l]];j++) ans = max(ans,a[j] + add[id[l]] < c ? a[j] + add[id[l]]: LONG_LONG_MIN);
        for(int j = L[id[r]];j <= r;j++) ans = max(ans,a[j] + add[id[r]] < c ? a[j] + add[id[r]] : LONG_LONG_MIN);
        for(int j = id[l] + 1;j < id[r];j++) {
          int pos = lower_bound(vec[j].begin(),vec[j].end(),c - add[j]) - vec[j].begin() - 1;
          if(pos >= 0) ans = max(ans,vec[j][pos] + add[j]);
        }
      }
      cout << (ans == LONG_LONG_MIN ? -1 : ans) << '\n';
    }
  }
  return 0;
}

数列分块5

开方运算有个奇妙的性质，那就是元素衰减很快，一直到 0/1 的时候开方无效。因为这个性质，可以发现很快就会有大量元素开方后不变，于是可以用懒标记维护，若某个区间已经变为 0/1 直接跳过即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int _ = 3e5 + 5; 

int n,blo;
int a[_];
int L[_],R[_],id[_],sq[_],sum[_];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
      sum[i] = sum[i] + a[j];
      sq[i] += (a[j] <= 1);
    }
  }
  for(int i = 1,op,l,r;i <= n;i++) {
    cin >> op >> l >> r;
    if(op == 0) {
      if(id[l] == id[r]) {
        if(sq[id[l]] < R[id[l]] - L[id[l]] + 1) {
          for(int j = l;j <= r;j++) {
            if(a[j] <= 1) continue;
            sum[id[l]] -= a[j];
            a[j] = sqrt(a[j]);
            sum[id[l]] += a[j];
            sq[id[l]] += (a[j] <= 1);
          }
        }
      } else {
        if(sq[id[l]] < R[id[l]] - L[id[l]] + 1) {
          for(int j = l;j <= R[id[l]];j++) {
            if(a[j] <= 1) continue;
            sum[id[l]] -= a[j];
            a[j] = sqrt(a[j]);
            sum[id[l]] += a[j];
            sq[id[l]] += (a[j] <= 1);
          }
        }
        if(sq[id[r]] < R[id[r]] - L[id[r]] + 1) {
          for(int j = L[id[r]];j <= r;j++) {
            if(a[j] <= 1) continue;
            sum[id[r]] -= a[j];
            a[j] = sqrt(a[j]);
            sum[id[r]] += a[j];
            sq[id[r]] += (a[j] <= 1);
          }
        }
        for(int j = id[l] + 1;j < id[r];j++) {
          if(sq[j] == R[j] - L[j] + 1) continue;
          for(int k = L[j];k <= R[j];k++) {
            if(a[k] <= 1) continue;
            sum[j] -= a[k];
            a[k] = sqrt(a[k]);
            sum[j] += a[k];
            sq[j] += (a[k] <= 1);
          }
        }
      }
    } else {
      int ans = 0;
      if(id[l] == id[r]) {
        for(int j = l;j <= r;j++) ans += a[j];
      } else {
        for(int j = l;j <= R[id[l]];j++) ans += a[j];
        for(int j = L[id[r]];j <= r;j++) ans += a[j];
        for(int j = id[l] + 1;j < id[r];j++) ans += sum[j];
      }
      cout << ans << '\n';
    }
  }
  return 0;
}

数列分块6

带插入，单点查询。考虑在一定时间内拍平整个区间维护并均摊。此时时间复杂度会降回 \sqrt n。

具体实现时，动态维护每一个块的元素，选取的时间点在 10\sqrt n 时可以通过此题。（单次拍平时间复杂度为 \Theta(\sqrt n) 较高，由于随机生成数据不必严格在 t=k\sqrt n 时拍平。

#include <bits/stdc++.h>
using namespace std;

const int _ = 3e5 + 5;

int n,blo;
int a[_];
vector<int> vec[10005];

int main() {
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
    vec[(i - 1) / blo + 1].push_back(a[i]);
  }
  int cnt = n;
  for(int i = 1,op,l,r;i <= n;i++) {
    cin >> op;
    if(op == 0) {
      cin >> l >> r;
      for(int j = 1;j <= cnt / blo + 1;j++) {
        if(vec[j].size() >= l) {
          vec[j].insert(vec[j].begin() + l - 1,r);
          break;
        }
        l -= vec[j].size();
      }
      cnt++;
    } else {
      cin >> l;
      for(int j = 1;j <= cnt / blo + 1;j++) {
        if(vec[j].size() >= l) {
          cout << vec[j][l - 1] << '\n';
          break;
        }
        l -= vec[j].size();
      }
    }
    if(i == blo * 10) {
      vector<int> tmp;
      for(auto &vecc : vec) {
        for(auto x : vecc) tmp.push_back(x);
        vecc.clear();
      }
      for(int j = 0;j < tmp.size();j++) {
        vec[j / blo + 1].push_back(tmp[j]);
      }
    }
  }
  return 0;
}

数列分块8

ODT 能做，但我们用分块解决。

由于修改操作只有推平，故在进行了很多次的时候很大概率一个块的所有值都是一样的。

维护每个块是否所有值都是相同的。若是，维护他们的共同值。

#include <bits/stdc++.h>
using namespace std;

const int _ = 3e5 + 5;

int n,blo;
int a[_];
int L[_],R[_],id[_],cov[_],covnum[_];

void Push(int x) {
  if(!cov[id[x]]) return;
  cov[id[x]] = 0;
  for(int i = L[id[x]];i <= R[id[x]];i++) a[i] = covnum[id[x]];
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
    cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
    L[i] = R[i - 1] + 1;
    R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
    for(int j = L[i];j <= R[i];j++) {
      id[j] = i;
    }
  }
  for(int i = 1,l,r,c;i <= n;i++) {
    cin >> l >> r >> c;
    int ans = 0;
    if(id[l] == id[r]) {
      Push(l);
      for(int j = l;j <= r;j++) ans += (a[j] == c),a[j] = c;
    } else {
      Push(l),Push(r);
      for(int j = l;j <= R[id[l]];j++) {
        ans += (a[j] == c);
        a[j] = c;
      }
      for(int j = L[id[r]];j <= r;j++) {
        ans += (a[j] == c);
        a[j] = c;
      }
      for(int j = id[l] + 1;j < id[r];j++) {
        if(cov[j]) ans += (covnum[j] == c) * (R[j] - L[j] + 1);
        else {
          for(int k = L[j];k <= R[j];k++) {
            ans += (a[k] == c);
          }
        }
        cov[j] = 1,covnum[j] = c;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

数列分块 9 要回滚莫队做（本质上也是分块）。我不会所以我就不写了。