前缀和
1.前缀和简介
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，(而差分可以看成前缀和的逆运算).合理的使用前缀和与差分，可以将某些复杂的问题简单化。
2.前缀和好处
求数组的某个区间的和时，最容易想出暴力算法，遍历区间求和，时间复杂度为O(n * m)
而使用前缀和进行求和的话，时间复杂度降到O(n + m)
3. 一维前缀和
首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
const int N = 10000;
int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
void qianzuihe (){
for (int i = 1; i < N;i++){
sum[i] = sum[i - 1] + a[i];
}
}
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl;//对数组区间[l,r]求和，时间复杂度为O(1)
-
原理
sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] ...... a[r];
sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];
sum[r] - sum[l - 1] = a[l] + a[l + 1] + ......+ a[r];
4.二维前缀和
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
同一维前缀和一样，我们先来定义一个二维数组s[] [] , s[i] [j] 表示二维数组中，左上角(1, 1)到右下角(i, j)所包围的矩阵元素的和。接下来推导二维前缀和的公式。
- 求s[i] [j]前缀和数组（预处理）
紫色面积是指(1, 1)左上角到(i, j - 1)右下角的矩形面积, 绿色面积是指(1, 1)左上角到(i - 1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。
从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i - 1][j] + 紫色面积s[i][j - 1] - 重复加的红色的面积s[i - 1][j - 1] + 小方块的面积a[i][j];
因此得出二维前缀和预处理公式
s[i][j] = s[i - 1][j] + s[i][j - 1 ] + a[i] [j] - s[i - 1][j - 1]
const int N = 10000;
int sum[N][N], a[N][N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
void qianzuihe (){
for (int i = 0; i < N;i++){
for (int j = 0; j < N;j++){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
}
- 求求以
(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和
紫色面积是指 (1, 1)左上角到(x1 - 1, y2)右下角的矩形面积 ，黄色面积是指(1, 1)左上角到(x2, y1 - 1)右下角的矩形面积；
绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1]
因此二维前缀和的结论为：
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x2, y1 - 1] - s[x1 - 1, y2] + s[x1 - 1, y1 - 1]
int x1, y1, x2, y2;
int main(){
cin >> x1 >> y1 >> x2 >> y2;
cout << '('<<x1 <<','<< y1<< ')' <<'('<<x2 <<','<< y2<<')' << endl;
cout << sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]<<endl;
}
总结
前缀和是一个非常有用的知识点，常用于解决一些涉及数组或列表的问题。前缀和的概念很简单：对于一个数组，如果我们要知道从索引0到当前位置的元素之和，我们只需要将当前位置的元素加上前面所有元素的和。这个和就是前缀和。
前缀和的优点是可以显著降低时间复杂度。例如，如果我们想找到一个数组中的累计和，使用前缀和可以在O(n)的时间复杂度内完成，而不用遍历整个数组。
在编程中，我们可以通过以下方式计算前缀和：
使用循环：遍历数组，每次计算从0到当前位置的元素之和。
使用数据结构：如使用哈希表或前缀和数组。对于这种数据结构，我们需要遍历一次数组来
计算前缀和，但之后查询前缀和的时间复杂度就是O(1)。