所谓前缀和就是前n个数的总和，预处理以后可以通过b[r]-b[l-1]得出由l到r的值。
1.一维前缀和
比较简单不多赘述。
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() { 6 int a[100], b[100]; 7 int n, l, r; 8 cin >> n; 9 cin >> l >> r; 10 //打表 11 for(int i = 1; i <= n; i++) { 12 cin >> a[i]; 13 } 14 b[1] = a[1]; 15 for(int i = 2; i <= n; i++) { 16 b[i] = b[i-1] + a[i]; 17 } 18 19 for(int i = 1; i <= n; i++) { 20 cout << b[i] << " "; 21 } 22 cout << endl; 23 24 cout << b[r]-b[l-1]; 25 return 0; 26 }
2.二维前缀和
预处理状态转移方程：b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]，下图很形象的表示出了这个式子。
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() { 6 int a[100][100], b[100][100]; 7 int n, m, x1, x2, y1, y2; //假设x2>x1, y2> y1 8 cin >> n >> m; 9 cin >> x1 >> y1 >> x2 >> y2; //从b[x1][y1]到b[x2][y2] 10 for(int i = 1; i <= n; i++) { 11 for(int j = 1; j <= m; j++) 12 cin >> a[i][j]; 13 } 14 15 //打表 16 memset(b, 0, sizeof(b)); //这个不要忘记 17 for(int i = 1; i <= n; i++) { 18 for(int j = 1; j <= m; j++) 19 b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]; 20 } 21 22 cout << b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] + b[x1-1][y1-1]; 23 return 0; 24 }
3.差分
差分：对于数列 a，其第 i 个元素和第 i - 1 个元素的差称为数列 a 第 i 项的差分。
表达式： b[i] = a[i] - a[i - 1]
对差分数组求前缀和就可以得到原数列a :sumb[i] = b[1] + b[2] + ... b[i] = a[1] + a[2] - a[1] + ... + a[i] - a[i - 1] = a[i]
简单应用：对从l到r的数组进行批量加减。
最简单的做法就是对于修改操作逐一加上 p，对于查询操作可以用前面的前缀和来求。但这样会t。其实我们可以拿差分数组做文章，每次只修改差分数组的两个端点即可，见下面的图解举例：
1.先求出差分序列
2.给定区间的头元素+p
3.给定区间的尾元素的下一个元素-p
4.求出区间和，反推原数组
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() { 6 int n, l, r, d, a[100], b[100], sum[100]; 7 cin >> n; 8 cin >> l >> r >> d; //从l到r,增加d 9 for(int i = 1; i <= n; i++) cin >> a[i]; 10 //差分数组 11 b[1] = a[1]; 12 for(int i = 2; i <= n; i++) b[i] = a[i] - a[i-1]; 13 for(int i = 1; i <= n; i++) cout << b[i] << " "; 14 cout << endl; 15 //通过差分数组求原数组 16 sum[1] = b[1]; 17 for(int i = 2; i <= n; i++) sum[i] = sum[i-1] + b[i]; 18 for(int i = 1; i <= n; i++) cout << sum[i] << " "; 19 cout << endl; 20 //原数组增加d后再由差分数组求原数组 21 b[l] += d; 22 b[r+1] -= d; 23 sum[1] = b[1]; 24 for(int i = 2; i <= n; i++) sum[i] = sum[i-1] + b[i]; 25 for(int i = 1; i <= n; i++) cout << sum[i] << " "; //这块可以设计成函数但是我懒得捣鼓了 26 return 0; 27 }