景德镇市网站建设_网站建设公司_交互流畅度_seo优化

前提提要：这两种算法都不用背，重点是理解，等题目需要时，自己画图解决！

注意不管是前缀和还是差分 我们一定要数组下标从1开始！

前缀和（分成一维和二维）

作用：求一段序列的和

一维前缀和：

题目原先数组a[N];

创建一个数组发前缀和数组f[N],利用for循环+递归 f[i]=f[i-1]+a[i];

假如题目要我们求[L,R]之间的和，我们可以用 sum=f[R]-f[L-1];

二位前缀和：

题目原先数组a[N][N];

第一步预处理：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i-1][j-1];

第二步求[x1,y1]到[x2,y2]之间的前缀和，即sum=f[x2][y2]-f[x2][y1-1]-f[x1-1][y2]+f[x1-1][y1-1];

差分（分一维和二维）

作用：对一段序列进行加x

一维差分：

有两种常用表达形式：

第一种：题目原先数组a[N],创建差分数组f[N],我们可以for循环 f[i]=a[i]-a[i-1];

对于题目要求改变的序列[L,R]，我们f[L]+=x,f[R-1]-=x;

然后还原原先序列 for循环 a[i]=a[i-1]+f[i] 输出即可得到新序列

第二种：根据性质来创建差分序列

for循环 我们直接输入一个t 再加上这两个表达式 f[i]+=t，f[i+1]-=t;

对于题目要求改变的序列[L,R]，我们f[L]+=x,f[R-1]-=x;

然后还原原先序列 for循环+前缀和还原 f[i]+=f[i-1];

一边常用第二种 因为可以少创建一个数组

二维差分：

我们对于[x1,y1]到[x2,y2]这个区间同时加x;

说明insert函数：f[x1][y1]+=x,f[x1][y2+1]-=x,f[x2+1][y1]-=x,f[x2+1][y2+1]+=x;

第一步：预处理 依次对二维数组cin>>t 我们就可以两个for循环 insert(i,j,i,j,t)

第二步：改变 insert(x1,y1,x2,y2,x);

第三步还原：用前缀和 sum=f[x2][y2]-f[x2][y1-1]-f[x1-1][y2]+f[x1-1][y1-1]；