分块算法 | Notion

int n;
ll a[N];
int L[M], R[M], B[N];
ll sum[M], tag[M];
int s, sz;
void init() {
	s = sqrt(n);
	sz = (n+s-1)/s;
	for (int i=1; i<=n; i++) {
		B[i] = (i-1)/s+1;
		sum[B[i]] += a[i];
	}
	for (int i=1; i<=sz; i++) {
		L[i] = (i-1)*s+1;
		R[i] = min(n, i*s);
	}
}

void add(int l, int r, ll val) {
	int x = B[l], y = B[r];
	if (x == y) {
		for (int i=l; i<=r; i++) {
			a[i] += val;
			sum[x] += val;
		}
	} else {
		for (int i=l; i<=R[x]; i++) {
			a[i] += val;
			sum[x] += val;
		}
		for (int i=L[y]; i<=r; i++) {
			a[i] += val;
			sum[y] += val;
		}
		for (int i=x+1; i<y; i++) {
			tag[i] += val;
		}
	}
}

ll ask(int l, int r, ll c) {
	int x = B[l], y = B[r];
	ll rt = 0;
	if (x == y) {
		for (int i=l; i<=r; i++) {
			rt += a[i] + tag[x];
		}
	} else {
		for (int i=l; i<=R[x]; i++) {
			rt += a[i] + tag[x];
		}
		for (int i=L[y]; i<=r; i++) {
			rt += a[i] + tag[y];
		}
		for (int i=x+1; i<y; i++) {
			rt += sum[i] + tag[i]*s;
		}
	}
	return rt%c;
}

分块算法主要思想

将长度为n的序列分为$\sqrt{n}$，对于区间的更新和查询都将对最多两个非完整块和$\sqrt{n}$个块操作

对非完整块可以直接暴力那么最多只需要$O(\sqrt{n})$时间复杂度，对单个完整块操作需要保证$O(1)$$O(log(\sqrt{n}))$时间复杂度，这样$\sqrt{n}$个块的时间复杂度在$\sqrt{n}$ 或 $\frac{\sqrt{n}}{2}log(n)$，当然其实对所有完整块可以直接暴力但是要保证暴力的次数很少。