【蓝桥每日一题]-前缀和与差分（保姆级教程 篇1）
目录
简介：
前缀和：
差分：
简介：
前缀和：
前缀和指一个数组的某下标之前的所有数组元素的和（即数列的前n项求和），前缀和是一种重要的预处理，能够降低算法的时间复杂度，可以快速地求出某一段的和，对于处理区间之间的问题是往往十分高效
差分：
差分实际上就是构建一个数组，让原数组是差分数组的前缀和数组
额，暂且就讲这么直白点吧，讲的太深了你又听不懂了。只要知道什么时候去用它们就行了。最重要的还是在应用中去体会！
上模板：
前缀和：
前缀和用于求区域的元素和
（注意：前缀和数组，我建议你一定要开long long，不然容易越界）
一维前缀和：
for(int i=1;i<=n;i++)
suf[i]=suf[i-1]+a[i];我建议你a[0]不要放元素，这样子初始化更方便，哈哈哈
二维前缀和：
这个是创建前缀和的一个从(1,1)到(i，j)的 “和矩阵”。
比如suf[1][1]就直接等于a[1][1]，suf[2][2]就等于a[1][1],a[1][2],a[2][1],a[2][2]，类似这种的矩阵
void create_suf(){
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
suf[i][j]=a[i][j]+suf[i-1][j]+suf[i][j-1]-suf[i-1][j-1];
}
}我也建议你a[ ][ ]也是从(1,1)开始放元素，这样初始化很方便。
这个是获取从(x1,y1)到(x2,y2)对角线内元素的和，注意是闭区间的(我已经打注释了)
int get_suf(int x1,int y1,int x2,int y2){//左右都是闭区间
return suf[x2][y2]-suf[x2][y1-1]-suf[x1-1][y2]+suf[x1-1][y1-1];
}
上面两部分就是核心代码（俗称板子，这是我最常用的板子，经过优化后，还算简短美观的！）！好了，下面是完全的使用代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[4][4]; //二维前缀和（起点必须从1,1开始，这样简单）
ll suf[4][4];
void create_suf(){
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
suf[i][j]=a[i][j]+suf[i-1][j]+suf[i][j-1]-suf[i-1][j-1];
}
}
int get_suf(int x1,int y1,int x2,int y2){//左右都是闭区间
return suf[x2][y2]-suf[x2][y1-1]-suf[x1-1][y2]+suf[x1-1][y1-1];
}
int main(){
int cnt=1;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
a[i][j]=cnt++;//给a数组随机赋值
}
}
create_suf();
cout<<get_suf(2,2,3,3)<<'\n'<<get_suf(1,2,2,3);
}
差分：
差分用于求数据多次变动后的结果，后者是前者的进阶用法，但公式差不多，你可以仔细体会一下
（注意： suf数组必须开ll dif数组必须多开一层 二维前缀和或差分必须从1,1开始）
一维差分：
核心模板：数据变动部分（从x下标到y下标都加z）
void add(int x,int y,int z){
suf[x]+=z;suf[y+1]-=z;//因为x到y都要加z
}
完整代码 ：（相当于一口气把3个数据变化操作全做了，这就是为什么差分快速的原因）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll suf[6]; //这个数组既是dif也是suf，必须多开一层，且用ll
void add(int x,int y,int z){
suf[x]+=z;suf[y+1]-=z;//因为x到y都要加z
}
int main(){
int a[5]={1,2,3,4,5}; //一维差分
add(2,4,5);//从2到5的元素都加5
add(1,3,2);//从1到3元素都加2
add(0,2,-3);//都-3
for(int i=1;i<5;i++){
suf[i]+=suf[i-1];
}
for(int i=0;i<5;i++){
a[i]+=suf[i];
}
}
二维差分：
模板：这里是数据变动部分（从(x1,y1)到(x2,y2)都变动z）
void add(int x1,int y1,int x2,int y2,int z){ //dif的作用在后面元素(可能用不到)，所以才让你多开一层
dif[x1][y1]+=z;dif[x2][y2+1]-=z;dif[x2+1][y2]-=z;dif[x2+1][y2+1]+=z;
}注意：我也注释了，就是dif总要在x2和y2后面加上对前面加z的抵消，故才让你多开一层dif数组
这里是由dif数组转为suf数组，相当于一口气处理了所有的数据变动，然后再加给原数组即可
void create_suf(){
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
suf[i][j]=dif[i][j]+suf[i-1][j]+suf[i][j-1]-suf[i-1][j-1];
}
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
a[i][j]+=suf[i][j];
}
}
上面就是模板，下面是完整代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[4][4],dif[5][5]; //dif要多开一层
ll suf[4][4];
void add(int x1,int y1,int x2,int y2,int z){ //dif的作用在后面元素(可能用不到)，所以才让你多开一层
dif[x1][y1]+=z;dif[x2][y2+1]-=z;dif[x2+1][y2]-=z;dif[x2+1][y2+1]+=z;
}
void create_suf(){
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
suf[i][j]=dif[i][j]+suf[i-1][j]+suf[i][j-1]-suf[i-1][j-1];
}
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
a[i][j]+=suf[i][j];
}
}
int main(){
int cnt=1;
for(int i=1;i<=3;i++){ //从(1,1)开始存
for(int j=1;j<=3;j++){
a[i][j]=cnt++;
}
}
add(1,1,3,2,3);
add(2,2,3,3,-1);
create_suf();
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++) cout<<a[i][j]<<' ';
cout<<'\n';
}
}
下面就开始练题了，不管是什么事情，实操才是最重要的