一维前缀和
sum[i]=sum[i-1]+a;
sum[i]为从1到i的和，它等于上一个和加当前数字，也就是sum[i-1]+a;
当我们要计算一个区间内的和时，如n到m，我们可以将其转化为从1到m减去1到n-1
也就是sum[m]-sum[n-1]
二维前缀和
- 准备一个sum数组记录从1，1到i，j之间的所有数字和
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a; //记录i,j 矩阵的和
输出左上角为x1,y1，右下角为x2, y2矩阵的和
sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]；
sum[x2][y2]为从1，1到x2，y2的和
sum[x1-1][y2]和sum[x2][y1-1]为其多余部分
sum[x1-1][y1-1]为重复扣除部分，需补上
一维差分
d[i]=a[i]-a[i-1]; //差分数组
d[l]+=c;
d[r+1]-=c;
循环读入要加的数c
求出差分数组d的前缀和数组
d[i]=d[i-1]+d[i];
二维差分
d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; //差分数组
for(int i=1;i<=q;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
d[x1][y1]+=1;
d[x2+1][y1]-=1;
d[x1][y2+1]-=1;
d[x2+1][y2+1]+=1;
}
循环读入要加的数c
d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
求出差分数组d的前缀和数组
双指针
用来优化时间复杂度
两个变量，如i，j，把它们当成两个指针
i，j依照题意从某一个地方出发，如一个一维数组，i从1出发，j从n出发
之后按照题意判断它们两个怎么移动
模板：
for(){ //枚举左端点
while() //防止右端点<左端点
while() // 移动右端点，只维护你想要的东西
if() //判断是否满足条件，如果是，则更新答案
//之后再移动左端点，维护你想要的东西
}