目录
什么是前缀和？
前缀和可以将数组中的连续元素相加
sum是数组中第一个元素到第i个元素的和
感觉像是简单的dp?
如何计算前缀和？
很简单，只要遍历一遍数组，每次将a中当前元素加到上一个前缀和上
时间复杂度是O（N）
代码：
#include <iostream>
#include <vector>
using namespace std;
int main() {
//原数组
vector<int> a = { 1, 2, 3, 4, 5 };
//前缀和数组
vector<int> sum(a.size());
sum[0] = a[0];
//计算前缀和
for (int i = 1; i < a.size (); i++) {
sum[i] = sum[i - 1] + a[i];
}
// 输出前缀和数组
for (int i = 0; i < a.size (); i++) {
cout << sum[i] << " ";
}
cout << endl;
return 0;
}当然也可以用库函数，不过作者感觉没什么用（需要对库函数掌握得十分滴熟练）
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main() {
vector<int> arr = { 1,2,3,4,5 };
vector<int> sum(arr.size());
partial_sum(arr.begin(), arr.end(), sum.begin());
for (int i = 0; i < arr.size(); i++)cout << sum[i] << " ";
return 0;
}在某些情况下还能再简单，即在原数组中计算，减少空间复杂度
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = { 1, 2, 3, 4, 5 };
int n = a.size();
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + a[i];
}
for (int num : a) {
cout << num << " ";
}
return 0;
}前缀和有什么用？
1、区间求和
给定一个区间,例如【1，3】，求数组在此区间上的和
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = { 1, 2, 3, 4, 5 };
vector<int> sum(a.size());
int left = 1;
int right = 3;
sum[0] = a[0];
for (int i = 1; i < a.size (); i++) {
sum[i] = sum[i - 1] + a[i];
}
//求区间和
cout << (sum[right] - sum[left-1]) << endl;
return 0;
}这里有一个特例，就是当left为0的时候，left-1就越界了
提供两个解决方法，一个是用if(left==0)特判，另一个是原数组从下标为1的位置开始存储（推荐）
注意不能写成sum[right] - sum[left]
2、前缀积（和前缀和差不多）
求区间【1，3】的前缀积就是sum[right]-sum[left-1]
前提是前缀积不能溢出
高精度计算中通常会对前缀积进行取模
sum[i]=(sum[i-1]*arr[i])%mod
感兴趣的可以搜一下乘法逆元/费马小定理/快速幂（其实是作者不会）
3、异或和
求区间【1，3】的异或和就是sum[right]^sum[left-1]
#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> arr = { 2,2,7,5,7,2,1,4,1,5 };
vector<int> s(arr.size());
s[0] = arr[0];
for (int i = 1; i < arr.size(); i++) {
s[i] = s[i - 1] ^ arr[i];
}
for (int i = 0; i < arr.size(); i++) {
cout << s[i] << " ";
}
return 0;
} 
前缀异或和数字相同=这段区间异或和为0
比如上图异或和中有2个7，就代表原数组5，7，2这3个数的异或和为0
实战
二维前缀和
#include<iostream>
#include<vector>
using namespace std;
int a[1050][1050], dp[1050][1050];
int main() {
int n, m, c;
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + a[i][j];
}
}
int x = 0, y = 0;
int MAX = -2147483648;
for (int i = c; i <= n; i++) {
for (int j = c; j <= m; j++)
{
int t = dp[i][j] - dp[i - c][j] - dp[i][j - c] + dp[i - c][j - c];
if (t > MAX) {
MAX = t;
x = i - c + 1;
y = j - c + 1;
}
}
}
cout << x << " " << y << endl;
return 0;
}
