专栏文章

分块

llunivia
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvupol
此快照首次捕获于
2025/12/02 09:11
3 个月前
此快照最后确认于
2025/12/02 09:11
3 个月前
查看原文

引入

分块，一种根号实现。使用它可以轻松完成一些 log⁡\log 数据结构需要很久才能完成/实现比较困难的东西，在 n≤2e5n\le 2e5 时候可以考虑尝试使用。
分块基本实现思路是，将块分成 bloblo 块。对于区间维护信息 [l,r][l,r]，实现以下做法：
  1. 目前元素所在的块不被完整包含在 [l,r][l,r] 内，那么暴力维护。
  2. 目前元素所在的块被完整包含在 [l,r][l,r] 内，即 a∈[Lx,Rx],[Lx,Rx]⊂[l,r]a\in [L_x,R_x],[L_x,R_x]\subset [l,r]（其中，Lx,RxL_x,R_x 是块 xx 的左右端点），那么则对目前块维护懒标记，就像线段树一样。单个块时间复杂度一般情况下为 Θ(1)\Theta(1)，故时间复杂度为 Θ(nblo)\Theta(\frac{n}{blo})。
单次修改/查询时间为 2∗Θ(blo)+Θ(nblo)=Θ(nblo+blo)2*\Theta(blo)+\Theta(\frac{n}{blo})=\Theta(\frac{n}{blo}+blo)。使用均值不等式： nblo+blo≥2n\frac{n}{blo}+blo\ge2\sqrt n，即当 nblo=blo→blo=n\frac{n}{blo}=blo\rightarrow blo=\sqrt n 时取到最小值。故一般情况下 bloblo 取 n\sqrt n 时间复杂度最优，为 Θ(qn)\Theta(q\sqrt n)。
这里使用数列分块的一些题目展示分块的实现和基本的 trick。

基本题

数列分块1

区间加，单点查。
维护两个值 sum,addsum,add 分别为每个块的总和和懒标记加。
CPP
#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,addsum,add 即可。
注：这里维护了 Lx,RxL_x,R_x，因为 sqrt(n)sqrt(n) 是向下取整，所以剩下不够的再单独分一个块。
CPP
#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 操作时由于是每个数乘 xx，故 add 也要乘 xx。
CPP
#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⁡\log 复杂度无法轻易做出的，但分块可以，因为分块本质上是暴力优化。

数列分块2

单点加，区间寻找小于 c2c^2 的数的个数。
考虑对于每个块维护一个排序版本 bib_i，然后左右不完整块暴力查询，中间使用 lower_boundlower\_bound 或手写二分查询。每次左右的时候都要重新覆盖一次数组。完整块时间复杂度为 log⁡blo\log blo。完整块加法时候不需要排序，因为不会改变原来相对位置。
CPP
#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

跟上面大同小异。
CPP
#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 直接跳过即可。
CPP
#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

带插入，单点查询。考虑在一定时间内拍平整个区间维护并均摊。此时时间复杂度会降回 n\sqrt n。
具体实现时，动态维护每一个块的元素，选取的时间点在 10n10\sqrt n 时可以通过此题。（单次拍平时间复杂度为 Θ(n)\Theta(\sqrt n) 较高，由于随机生成数据不必严格在 t=knt=k\sqrt n 时拍平。
CPP
#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 能做，但我们用分块解决。
由于修改操作只有推平，故在进行了很多次的时候很大概率一个块的所有值都是一样的。
维护每个块是否所有值都是相同的。若是，维护他们的共同值。
CPP
#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 要回滚莫队做（本质上也是分块）。我不会所以我就不写了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...