分块

分块的思想就是将一大段数据分成若干个整段来达到快速维护和查询的效果。运用了懒标记的思想。

最简单的例子如题 一个简单的整数问题

#include <cstdio>
#include <cmath>
#define orz(i,a,b) for (int i = a;i <= b; i++)
#define sto(i,a,b) for (int i = a;i >= b; i--)
using namespace std;
const int N = 2e5 + 5, M = 500 + 5;
int n, m;
long long a[N], add[M], sum[M];//add为懒标记，sum[i]为第 i 块中所有数的总和。a[i]的真实值为a[i]+add[p[i]] 
int p[N], len;//p[i]是i所对块的编号，len是每个块的长度 
void change (int l, int r, long long d) {//修改操作 
	if (p[l] == p[r]) {    //l,r处于同一块之中 
		orz (i, l, r) {    //暴力处理 
			a[i] += d;
			sum[p[i]] += d;
		}
	}
	else {
		int i = l, j = r;
		while (p[i] == p[l]) {//左右零散的用暴力处理 
			a[i] += d;
			sum[p[i]] += d;
			i++;
		}
		while (p[j] == p[r]) {
			a[j] += d;
			sum[p[j]] += d;
			j--;
		}
		orz (k, p[i], p[j]) {//整块的就打上懒标记 
			sum[k] += len * d;
			add[k] += d;
		}
	}
}
long long query(int l, int r) {//查询操作 
	long long ans = 0;
	if (p[l] == p[r]) {//l,r处于同一块 
		orz (i, l, r)  //暴力求解 
			ans += a[i] + add[p[i]];
	}
	else {
		int i = l, j = r;
		while (p[i] == p[l]) {//左右的零散用暴力累加 
			ans += a[i] + add[p[i]];//注意真实值为a[i]+add[p[i]] 
			i++;
		}
		while (p[j] == p[r]) {
			ans += a[j] + add[p[j]];
			j--;
		}
		orz (k, p[i], p[j])//整块的直接加sum 
			ans += sum[k];
	}
	return ans;
}
int main() {
	scanf ("%d%d", &n, &m);
	len = sqrt(n);
	orz (i, 1, n) {
		scanf ("%lld", a + i);
		p[i] = (i - 1) / len;//(i-1)/len使得每一块(除最后一块)都有len个数 
		sum[p[i]] += a[i];
	}
	while (m--) {
		char op;
		scanf (" %c", &op);//%c前加' '可以过滤空格和换行等字符 
		if (op == 'C') {
			int l, r;
			long long k;
			scanf ("%d%d%lld", &l, &r, &k);
			change(l, r, k);
		}
		else {
			int l, r;
			scanf ("%d%d", &l, &r);
			printf ("%lld\n", query(l, r));
		}
	}
	return 0;
}

因为每一块最多为 $\sqrt{N}$ ,所以所有散块的暴力操作时间复杂度为 $O(\sqrt{N})$ 又因为总共只有 $\sqrt{N}$ 块，所以整块的操作时间复杂度也为 $O(\sqrt{N})$ ，所以整个算法的时间复杂度为 $O(M\sqrt{N})$。