一维前缀和
快速求某段区间里面的和
假设有一个长度为 n 的数组，a1，a2，a3，. . . an
前缀和数组 Si = a1 + a2 + . . . + ai，表示原数组中前 i 个数字的和
前缀和中一定要让下标从 1 开始
为了定义S0 = 0
①如何求前缀和数组 Si
定义边界值 S0 = 0，处理边界
假设要计算 a [1，10] 的和需要计算 S10 - S0 → a [1，10] 就是 S [10]，方便统一处理所有的情况
从前往后递推求 Si
for i = 1；i ≤ n；i ++
S [ i ] = S [ i - 1 ] + ai
S [ i ] 是通过 S [ i - 1 ] 计算得到的，S [ i - 1 ] 是 a 数组中前 i - 1个数的和，加上第 i 个数，得到前 i 个数的和 → S [ i ]
②Si 用来干嘛，前缀和数组的作用？
快速求出原数组中一段数的和，求原数组中 a [ L，R ] 这一段数的和：SR - SL-1
SR表示前 R 个数的和：SR = a1 + a2 + . . . + aL-1 + aL + . . . + aR
SL-1表示前 L-1 个数的和：SL-1 =?a1 + a2 + . . . + aL-1
一次运算可以计算出任意一段区间内所有数的和
输入样例：2?? 4
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100010;
int n,m;
int a[N],s[N];
int main()
{
scanf("%d%d",&n,&m);
//读入n个数
for(int i = 0;i <= n;i++) scanf("%d",&a[i]);
//前缀和的初始化-> 前i个数的和=前i-1个数的和+第i个数
for(int i=0;i <= n;i++) s[i] = s[i-1] + a[i];
//m个询问
while(m--)
{
scanf("%d%d",&l,&r);
//区间和的计算-> 前r个数的和-前l-1个数的和=第l个数到第r个数的和
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}二维前缀和
快速求某一个子矩阵的和
Si j：求 ( i ，j ) 这个点左上角的所有元素的和
求 ( x1，y1 ) 为左上角，( x2，y2 ) 为右下角的矩形内部的所有元素的和
x 是 行，y 是 列，前缀和数组下标一般从 1 开始
Si j 的面积、求和的两个公式推导如下
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1010;
//询问次数q
int n,m,q;
//原数组 前缀和数组
int a[N][N],s[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%d",&a[i][j]);
//求前缀和
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
//做q个询问
while(q--)
{
//左上角 右下角
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
//算子矩阵的和
printf("%d\n",s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
}
return 0;
}一维差分
前缀和的逆运算
给定原数组 a1，a2，. . .? an，构造 b 数组：b1，b2，. . . bn
构造 b 数组后，使得 a 数组是 b 数组的前缀和 ai = b1 + b2 + . . . + bi，则称 b 数组为 a 数组的差分，a 数组称为 b 数组的前缀和
b1 = a1
b2 = a2 - a1
b3 = a3 - a2
. . .
bn = an - an-1
差分有什么用？
对 b 数组求前缀和可以得到原数组 a，只要有 b 数组就可以用 O(n) 的时间复杂度得到 a 数组
用O(1) 的时间给原数组中间某一段连续区间，全部加上一个固定的值
在 a 数组中有一个区间 [ L，R ]，把这个区间内所有的数全部加上 c，aL + c，aL+1 + c，. . . aR + c? 暴力循环求解 O(n)
差分 只需要修改两个数 O(1)
如果想求原来的数组 a，只需要扫描 b 数组，对 b 数组求一遍前缀和即可
对原数组 a [ L ~ R ] 区间全部 + c，对 b 数组的影响：只要让 bL + c，aL ~ an 会全部加上 c （aL = b1 + b2 + . . . + bL），实
际上只要让 [ aL ~ aR ] + c，并且 R + 1 之后的数不能加上 c，让 bR+1 - c 即可
假定 a 数组初始时全部为 0，差分数组初始也全部是 0，看成进行了 n 次插入操作
让原数组中的 [ 1，1 ] 区间 + a1??????? 让原数组中的[ 2，2 ] 区间 + a2? ????? [ n，n ] + an . . .
?
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 100010;
//元素个数 操作个数
int n,m;
//原数组 差分数组
int a[N],b[N];
//在l~r之间加入c
void insert(int l,int r,int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
//插入原数组的n个数
for(int i = 1;i <= n;i++) insert(i,i,a[i]);
//m个操作
while(m--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
//求原来数组-> 对差分数组求前缀和 把b数组变成自己的前缀和
for(int i = 1;i <= n;i++) b[i] += b[i - 1];
for(int i = 1;i <= n;i++) printf("%d",b[i]);
return 0;
}二维差分
二维前缀和的逆运算
用O(1) 的时间给原矩阵其中的一个子矩阵，全部加上一个固定的值
假设有一个原矩阵ai j，给原矩阵构造差分矩阵 bi j，只要满足原矩阵 ai j 是差分矩阵 bi j 的前缀和即可，ai j 的左上角存的是所有 bi j 的和
构造方式不用考虑，可以假定 ai j 初始都是 0，bi j 也为 0，再遍历一遍原来矩阵中的值，做插入即可，只需要考虑如何更新
原来需要处理整个区间，现在只需要处理 4 个数据，把 O(n)? 的时间复杂度变成 O(1)
如果要求 ai j 的值只需要求 b 数组的前缀和即可
在 1 * 1 的矩阵中加上对应位置的值，在 n * m 的矩阵加上对应位置的值
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1010;
//长 宽 操作个数
int n,m,q;
//原矩阵 差分矩阵
int a[N][N],b[N][N];
//在l~r之间加入c
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2] += c;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%d",&a[i][j]);
//假定初始时a矩阵为空-> 把a矩阵的每一个数插到空数组中,如果n,m个数,相当于进行了n*m次操作
//把每个数做插入
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
insert(i,j,i,j,a[i][j]);
//进行q次操作
while(q--)
{
int x1,x2,y1,y2,c;
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
insert(x1,y1,x2,y2,c);
}
//求前缀和
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];
//输出
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++) printf("%d",b[i][j]);
put(" ");
}
return 0;
}