前缀和简析

前缀和

前置知识：\(\sum_{i = 1}^{r}{a_i} = a_l + a_{l + 1} + \dots + a_{r - 1} + a_r\)
考虑以下数组：

如果我们要查询 \(\sum_{i = 1}^{2}{a_i}\)，很显然可以得到 \(\sum_{i = 1}^{2}{a_i} = 3 + 5 = 8\)。如果我们要查询 \(\sum_{i = l}^{r}{a_i}\)，则每次的时间复杂度为 \(O(r -l)\)。
如果我们对于一个长度为 \(n\) 的数组查询 \(k\) 次（不修改），则时间复杂度为 \(O(nk)\) 。如果给定一个 \(n = 10^7,k = 10^6\)，我们要如何让程序在 1s 内运行完呢？

我们构造\(b_0 = 0,b_i = b_{i - 1} + a_i\)，同上表，倘若我们只考虑快速查询 \(\sum_{i = 1}^{r}{a_i}\)，显而易见原式即为 \(\sum_{i = 1}^{r}{a_i} = b_i\)，而 \(b\) 数组可以在\(O(n)\) 的时间范围内预处理完。简易证明见下：

\(b_i = b_{i - 1} + a_i = b_{i - 2} + a_{i - 1} + a_i = \sum_{i = 1}^{r}{a_i}\)

假如我们转换一下思路，可以发现 \(\sum_{i = l}^{r}{a_i} = \sum_{i = 1}^{r}{a_i} - \sum_{i = 1}^{l-1}{a_i} = b_r - b_{l - 1}\)，那么我们将单次查询复杂度降到了 \(O(1)\)，总时间复杂度变为 \(O(n + k)\)。

例题

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<algorithm>

using namespace std;

// 快读
inline int read() {
	int x = 0,f = 1;char ch = getchar();
	while (ch < '0' or ch > '9'){if (ch == '-') f = -1;ch = getchar();}
	while (ch >= '0' and ch <='9'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}
//快写
inline void write(int x) {
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
//输出char
void writec(char x) {
	putchar(x);
	return;
}
int main() {
	int n = read(),a[100005],m;
	for(int i = 1;i <= n;i++) a[i] = read() + a[i - 1];
	m = read();
	while(m--) {
		int l = read() - 1,r = read();
		write(a[r] - a[l]),writec('\n');
	}
    return 0;
}

差分

考虑完不修改多次查询，如果我们多次将区间内的所有数加上一个值，最后统一查询，那么会怎么样呢？
假设我们操作2次，第一次让 \(a_1 \dots a_3 \gets(a_1 + 3)\dots (a_3+3)\),第二次让 \(a_1 ，a_2 \gets(a_1 + 2)\dots (a_2+2)\)

如果你对这一些规律不太敏感的话，可以考虑 \(b_i = a_i - a_{i - 1}\)，那么：

显而易见，如果区间加减，\(b_i\) 只会改变两个值，切规律如下：

\(b_l \gets b_l + k,b_{r + 1} \gets b_{r + 1}- k\)。

我们将每次修改由 \(O(n)\) 变成了 \(O(1)\)。

例题

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<map>

using namespace std;
int x[10005];
// 快读
inline int read()
{
	int x = 0,f = 1;char ch = getchar();
	while (ch < '0' or ch > '9'){if (ch == '-') f = -1;ch = getchar();}
	while (ch >= '0' and ch<='9'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}
//快写
inline void write(int x) {
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
//输出char
void writec(char x) {
	putchar(x);
	return;
}
int main() {
	int t = read();
	while(t--) {
		int n = read(),u = read();
		for(int i = 0;i < n;i++) x[i] = 0;
		while(u--) {
			int l = read(),r = read(),val = read();
			x[l] += val;
			x[r + 1] -= val;
		}
		for(int i = 1;i < n;i++) x[i] += x[i - 1];
		int q = read();
		while(q--) {
			int i = read();
			write(x[i]),writec('\n');
		}
	}
    return 0;
}