本篇将介绍 前缀和 和 差分 算法。

前缀和

前缀和顾名思义，就是求出前缀的和。让我们从题目入手，当我们遇到下面的题目时：

题目示例

给定N个数，M个询问a，b，要求输出区间[a,b]的区间和。
样例输入：

1
2
3
4
5
6
5
3 7 4 9 2
3
2 3
1 4
4 5

样例输出：

1
2
3
11
23
11

这是一个标准的一位前缀和模板题 查询区间和，对于这样的题目使用暴力做法则需要O(NM)的时间复杂度。这实在是太慢了，那么我们需要使用前缀和来加快查询的速度。

对于长度为 nn 的序列 {aia_i} 根据下面的递推式构造一个 前缀和数组 S{a1,a1+a2,a1+a2+a3,...a_1,a_1+a_2,a_1+a_2+a_3,...}

𝑆0=0，𝑆𝑖=𝑆𝑖−1+𝑎𝑖𝑆_0=0，𝑆_𝑖=𝑆_{𝑖−1}+𝑎_𝑖

当我们需要查询区间和的时候，只需要计算区间两端的差值即可

Sum([𝑙,𝑟])=𝑆𝑟−𝑆𝑙−1.Sum([𝑙,𝑟])=𝑆_𝑟−𝑆_{𝑙−1}.

这样，我们使用 O(n)O(n) 的时间来预处理后，就可以使用 O(1)O(1) 的时间来查询：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n,m;
vector<int> a; //题目数组
vector<int> p; //前缀和数组

void pre() { //前缀和数组预处理
	p = a;
	for(int i = 1;i <= n;i++) {
		p[i] += p[i-1];
	}
}

int query(int l, int r) { //查询区间和
	return p[r] - p[l-1];
}

差分

前缀和对于多次求区间和可以大幅加快速度，但是遇到多次修改区间就不行了，由于每次修改都需要 O(n)O(n) 的时间去准备前缀和数组，这实在是太慢了。那么我们就需要换成差分来加快修改。

同前缀和一样，需要维护一个差分数组。对于长度为 nn 的序列 {aia_i} 构建一个 差分数组 D{a1,a2−a1,a3−a2,...a_1,a_2-a_1,a_3-a_2,...} 保存每一位数对于上一位数的差值。

𝑎0=0，𝐷𝑖=𝑎𝑖−𝑎𝑖−1𝑎_0=0，𝐷_𝑖=𝑎_𝑖−𝑎_{𝑖−1}

当我们需要查询 {aia_i} 时，只需要求 𝑎𝑖=∑j=1i𝐷𝑗𝑎_𝑖=\sum_{j=1}^{i}𝐷_𝑗 对于差分数组DiD_i，我们可以理解为 将i下标之后的的所有下标的数加上DiD_i

因此，当我们需要将 {𝑎𝑖𝑎_𝑖} 的区间 [l,r][l,r] 中的每个数都加上一个 vv 的时候，只需要对于差分数组的区间首加上 vv ，区间尾的后一个数减去 vv 即可。

Dl=Dl+v，Dr−1=Dr−1−vD_l = D_l+v，D_{r - 1} = D_{r - 1}-v

这样，我们就可以使用 O(1)O(1) 的时间来多次修改，使用 O(n)O(n) 的时间来查询结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n,m;
vector<int> a; //题目数组
vector<int> p; //差分数组

void pre() { //差分数组预处理
	p = a;
	for(int i = 1;i <= n;i++) {
		p[i] = a[i] - a[i-1];
	}
}

void add(int l, int r, int v) {
	p[l] += v;
	p[r + 1] -= v;
}

int query(int n) { //查询结果
	int ans;
	for(int i = 1;i <= n;i++) {
		ans += p[i];
	}
	return ans;
}