前段时间一直懒得更新，这两天更新一下顺带复习一下
二分啥的其实也应该放进这里面，不过既然已经写过了就算了
前缀和
一维前缀和
若原序列存储在a数组中，则在它的前缀和数组中当下标为i时sum[i]储存的是(a[1]+a[2]+.....+a[i])，即i之前（包括i）的所有元素的和，代码表示为sum[i]=sum[i-1]+a[i]。前缀和的优势在于可以O（1）计算出某个区间的和.
例如要求a[i]到a[j]之间所有数的和，即a[i]+a[i+1]+....+a[j]==sum[j]-sum[i-1];
例：洛谷P8218求区间和
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[i]=a[i-1]+x;
}
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",a[r]-a[l-1]);
}
return 0;
}
二位前缀和
和一维前缀和的思想类似但稍微麻烦了一些。由于数组是二维的因此我们也需要放在平面中进行考虑。首先是前缀和的预处理，将二维数组看做一个巨大的长方形，我们将sum[i][j]定义为以长方形左上角为左上顶点,(i,j)为右下顶点的长方形包含的所有店的权值和（可以理解为面积）
二维前缀和的公式是sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];就是一个大长方形减去两个长方形再加上多减去的部分，最后再加上该点的总和。画个图就很简洁了，不过因为我懒，就不在这儿画了。
二维前缀和的用途是可以求数组中任意一块区域的总和。由于任何形状的区域都是可以用长方形拼凑删减得来的，因此我们也只需要知道求一个长方形区域的前缀和公式即可。
假设我们要求一块边长为x的正方形区域的面积，和处理前缀和的时候类似。假设要求区域的右下角坐标为[i][j]，则区域面积为sum[i][j]-sum[i-c][j]-sum[i][j-c]-sum[i-c][j]+sum[i-c][j-c];
例：洛谷p2004领地选择
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1505][1505];
int main()
{
ll inf=1e16;
ll n,m,c;
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
ll x;
scanf("%lld",&x);
a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+x;
}
}
ll maxn=-inf,ansi,ansj;
for(int i=1;i<=n-c+1;i++)
{
for(int j=1;j<=m-c+1;j++)
{
int x=i+c-1,y=j+c-1;
if(x>n) x=n;if(y>m) y=m;
int c=a[x][y]-a[i-1][y]-a[x][j-1]+a[i-1][j-1];
// cout<<c<<' ';
if(maxn<c) {maxn=c;ansi=i,ansj=j;}
}
// cout<<endl;
}
printf("%lld %lld",ansi,ansj);
return 0;
}
差分
一维差分
差分是前缀和的逆运算，差分数组中c[i]=a[i]-a[i-1].易得a[i]==c[1]+c[2]+....+c[i];
例如一个序列为1 2 3 4 5
那他的差分数组就是1 1 1 1 1
那么我们要这么个数组有什么用呢？
还是上面的数组，我们将c[2]加上1变成2，序列变成1 2 1 1 1
然后我们如果再用求a[i]的公式，会发现这样计算出来的序列是1 3 4 5 6，也就是说第二位以及之后的数组全都加上了1.因此我们可以用差分数组来实现0(1)的局部数组加减。当然如果只有刚才那个操作的话我们只能对数组的某个后缀进行操作，因此我们想要实现对任意区间的修改的话需要抵消前面的影响。对于刚才进行过的操作而言，如果我们只想改变第二个和第三个数字，那我们只需要将c[4]-1即可。
即数组变成了1 2 1 0 1，计算得到的序列为1 3 4 4 5
即若想实现将l到r的区间整体加上x，需要先令c[l]-x,再令c[r+1]+x.
例：ACWing503 借教室
题目大意是一共有n天，并且每天有不同数量的教室空闲，你需要按顺序处理订单将教室借给别人，每份订单都将借走从l天到r天的固定数量的教室。当某天剩余教室不够时无法完成订单，需要取消订单，输出该订单编号即可。
每份订单可以看做对一个区间做减法，很容易想到差分。难点是在对于每个订单减去后，还要查出有没有哪一天的剩余教室是负数。一般在这时候就很容易陷入一个误区，就是觉得逐天检查不现实，因为那样就失去了差分的意义了。这种情况就是默认按顺序每进行一个订单就检查一次了，如果顺着这样想，基本就做不出来了
思路为对答案进行二分，直接判断处理到第x个订单有没有教室不够的情况。因为对于每个订单而言，只有在之前出现过教室不够和没出现过教室不够两种情况。对于每个订单要将它之前的所有订单全都重新再推算一遍，这时候就可以用差分进行0（1）的运算了。然后再O（n）把所有时间扫一遍看看有没有不够的日子。整体复杂度为O（nlogn）。需要注意的是，由于二分时有可能会向左半部分继续二分，因此差分数组要每次都更新
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e6+10;
int val[maxn];
int sum[maxn],cha[maxn];//差分数组以及差分数组前缀和，
int cost[maxn],beg[maxn],endd[maxn];
int check(int x)//订单x时是否成立
{
for(int i=1;i<=x;i++)
{
//for(int j=1;j<=n;j++) cout<<cha[j]<<' ';
//cout<<endl;
cha[beg[i]]-=cost[i];
cha[endd[i]+1]+=cost[i];
}
int flag=0;
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+cha[i];
cha[i]=val[i]-val[i-1];//初始化差分数组
// cout<<sum[i]<<' ';
if(sum[i]<0) flag=1;
}
if(flag) return 0;
//cout<<endl;
return 1;
}
int find(int l,int r)
{
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;//如果可以说明答案在后面
else r=mid;
}
if(check(l)) return 0;
else return l;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
cha[i]=val[i]-val[i-1];
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&cost[i],&beg[i],&endd[i]);
}
int ans=find(1,m);
if(ans) printf("-1\n%d",ans);
else printf("%d",ans);
return 0;
}
二维差分
和二维前缀和以及一维差分类似，当c[i][j]+v，则以(i,j)为左上端点的无限大的长方形区域都会加上v。如果想给特定区域加上v也和二维前缀和类似。
还是假设要给坐上顶点坐标（i，j）边长为c的正方形整体加v。则需要做以下几个操作
1.c[i][j]+=v;
2.c[i+c][j]-=v;
3.c[i][j+C]-=v;
4.c[i+c][j+c]+=v;
捋清楚其实还蛮简单的
那么如何进行二维差分数组的初始化呢？
arr是二维前缀和数组
你用吗？我不用。太麻烦了。
不如直接插入，比如c[1][1]就相当于插入一个左上顶点为（1,1）边长为1的正方形，直接套函数就行。
例题：还没写，未来可能会有