本次通过三道差分、前缀和题目进行展开：
B3612 【深进1.例1】求区间和 – 洛谷
本题是经典的一维前缀和，并不难想到，但为了铺垫之后的矩阵二维前缀和，这里对一维前缀和做个简单讲解后，直接给出该题的参考代码
我们定义一个数列 {an} 的前缀和为 Sn=i=1∑nai=a1+a2+⋯+an。
有了前缀和之后，我们可以使用差分来进行静态的区间求和。具体而言，对于一个区间 [l,r]，区间的和 al+al+1+⋯+ar=Sr−Sl−1。
证明的话直接展开，Sr=a1+a2+⋯+al−1+al+al+1+⋯+ar，Sl−1=a1+a2+⋯+al−1，这样 Sr−Sl−1 便等于 al+al+1+⋯+ar，即所求的区间和了，预处理出前缀和，单次就是 O(1) 复杂度可以完成的事情了。用图表示的话，由于是一维我们可以尝试使用长度表示，会更加直观
代码如下：
#include <iostream>
using namespace std;
int main(){
int n,m,l,r,i,j;
scanf("%d",&n);
int arr1[n+1],arr2[n+1];
arr1[0]=arr2[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&arr1[i]);
arr2[i]=arr1[i];
}
for(i=1;i<=n;i++){
arr2[i]+=arr2[i-1];
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d %d",&l,&r);
printf("%d\\n",arr2[r]-arr2[l-1]);
}
return 0;
}
B3693 数列前缀和 4 – 洛谷
这一题，就没有上题那么简单了，就是我们先前讲的二维矩阵前缀和，这需要我们将其抽象成面积来进行公式的计算：
该图来自该题题解中的大佬所展示，将图从左往右，自上而下，从分散到整体看成5块面积；
假设我们现在要求红色的面积，而这几何意义就是（c,a)->(d,b)的前缀和：
S2=S5-（S1+S3）-（S3+S4）+S3通过这个公式我们可以将其抽象成前缀和的公式
以上这个图的意义也可以用于设计每项前缀和的处理
而对于该题取
的模，可以使用unsigned long long型，这样只要达到上溢就会自动变为0（这个思想要记得！！！
我们先给出代码解释，然后对要点进行提炼分析：
#include <iostream>
#include <cstring>
using namespace std;
#define ull unsigned long long
ull sum[1005][1005];
int main(){
ios::sync_with_stdio(0);
cin.tie(NULL);
ull x,y,u,v;
ull ans,q,temp,i,j,T,m,n;
cin>>T;
while(T–){
memset(sum,0,sizeof(sum));
cin>>n>>m>>q;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>temp;
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+temp;
}
}
ans=0;
for(i=0;i<q;i++){
cin>>u>>v>>x>>y;
ans^=sum[x][y]-sum[u-1][y]+sum[u-1][v-1]-sum[x][v-1];
}
cout<<ans<<endl;
}
return 0;
}
1.关于输入输出的提速：
通常来讲，cin，cout的运行是会比printf和scanf更慢的，但是我们可以用代码，解除某些限制，然后达以提速目的，也就是上述的两行代码：
ios::sync_with_stdio(0);
cin.tie(NULL);
2.关于数组：
在竞赛中，动态数组并没有静态或全局好用，只要我们限制好数组最大元素值，会方便很多：
如这题开的最大元素值1005，在竞赛中是常见的最大元素值
3.memset函数：
可用于数组快速清0或全规定为1，但若规定成其它数字，很可能会出错，尽量只有需要全0或1的时候使用
格式：
memset（数组名，0/1，数组大小（想要清理的个数）；
CF816B Karen and Coffee – 洛谷
这是一题经典的差分＋前缀和的综合运用题，
根据差分和前缀和的定义，我们可以知道，差分和前缀和互为逆运算，也就是说对于原数组，我们只要进行一次差分，再进行一次前缀和，就能得到区间变化后的原数组
而对于区间更新原理，只要在端点+v即可，这是因为，在之后的前缀和累加时，
arr[i]+=arr[i-1],i项它在变回原数组的时候，也会有+v的效果
所以通过以上的解释，我们可以了解到：
差分数组的核心优势是将区间更新转化为两点更新，在需要频繁更新区间的场景中，他是一个非常优秀的处理数据的方案
代码如下：
#include <iostream>
using namespace std;
int arr[200005];
int main(){
int n,k,q,l,r,c;
cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>l>>r;
arr[l]++;
arr[r+1]–;
}
for(int i=1;i<=200001;i++){
arr[i]+=arr[i-1];
}
for(int i=0;i<q;i++){
c=0;
cin>>l>>r;
for(int j=l;j<=r;j++){
if(arr[j]>=k) c++;
}
cout<<c<<endl;
}
return 0;
}
至此，今日的学习记录就到这里了！
