一、基础知识

1. 前缀和

前缀和（又叫积分）：在一个数字组成的序列中从位置 $1$ 到位置 $n$ 这个区间内的所有数字之和。

例如：

${\mathtt{a}}_{\mathtt{i}}$	1	2	3	4	5	6	7	8
$\mathtt{pf}{\mathtt{x}}_{\mathtt{i}}$	1	3	6	10	15	21	28	36

前缀和可以大大提高查询区间和的时间复杂度。如果按照普通的 for 循环，时间复杂度为 $O(r-l+1)$，使用前缀和后套用公式 $\mathtt{pf}{\mathtt{x}}_{\mathtt{r}}-\mathtt{pf}{\mathtt{x}}_{\mathtt{l}-1}$，就可以直接用 $O(1)$ 的时间复杂度获得答案。

2. 差分

差分：求相邻两个元素的差值并存储，也是前缀和的逆运算。

例如：

${\mathtt{a}}_{\mathtt{i}}$	1	3	6	10	15	21	28	36
$\mathtt{dif}{\mathtt{f}}_{\mathtt{i}}$	1	2	3	4	5	6	7	8

3. 公式

3.1 一维

3.2 二维

二维前缀和：$$\mathtt{pf}{\mathtt{x}}_{\mathtt{i},\mathtt{j}}=\mathtt{pf}{\mathtt{x}}_{\mathtt{i}-1,\mathtt{j}}+\mathtt{pf}{\mathtt{x}}_{\mathtt{i},\mathtt{j}-1}-\mathtt{pf}{\mathtt{x}}_{\mathtt{i}-1,\mathtt{j}-1}+{\mathtt{a}}_{\mathtt{i},\mathtt{j}}$$
二维区间和：$$\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_2,{\mathtt{y}}_2}-\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_1-1,{\mathtt{y}}_2}-\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_2,{\mathtt{y}}_1-1}+\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_1-1,{\mathtt{y}}_1-1}$$

---

二维差分区间范围统一+1：$$\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_1,{\mathtt{y}}_1}+1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_1,{\mathtt{y}}_2+1}-1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_2+1,{\mathtt{y}}_1}-1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_2+1,{\mathtt{y}}_2+1}+1$$

---

用差分数组求前缀和就可以获得原数组。

二、基础运用

1. 堆积成山的书

1.1 审题

有两叠书，分别有 $N$ 和 $M$ 本。
看完第一叠自顶向下第 $i$ 本书需要 $A_i$ 分钟，看完第二叠自顶向下第 $i$ 本书需要 $B_i$ ​分钟。
你每次可以花时间看完任意一叠书（不为空）的最上面那一本书，然后把它移除。
问你在 $K$ 分钟内最多能看完几本书？

1.2 分析

我们可以使用前缀和数组 pfx[]，更方便地计算累积时间。这道题的突破口是通过遍历第一叠书和第二叠书，找到能在限定时间内看完的最大本数。

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+8;
ll n,m,k,pfx[MAXN];
int main(){cin>>n>>m>>k;for(int i=1,a;i<=n;i++){cin>>a;pfx[i]=pfx[i-1]+a;}ll sum=0,idx=n,ans;//sum:第二叠书的总时间,idx:第一叠书的剩余本数//尝试让第一叠书能够在时间限制内看完的最大本数while(idx>0&&pfx[idx]>k)idx--;// 少看一本}ans=idx;//第一叠书的前idx本书//逐本判断第二叠书能否在时间限制内看完，并更新答案for(int i=1,b;i<=m;i++){cin>>b;sum+=b;//累加第二叠书的时间//判断第一叠书是否能在时间限制内看完while(idx>=0&&pfx[idx]+sum>k)idx--;if(idx==-1)break;//如果第一叠书已经无法看完，跳出循环ans=max(ans,idx+i);//更新答案}cout<<ans;//输出答案return 0;
}

2. 皮皮过马路

2.1 审题

每天放学的时候，皮皮和他的朋友们都会穿过校门口的马路。
考虑皮皮的学校在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 $y=0$ 描述，另一侧由直线 $y=1$ 描述。
第 $i$ 个小朋友从马路一侧的位置 $(a_i,0)$ 沿直线过马路到达另一侧的位置 $(b_i,1)$。
所有 $a_i$ 互不相同，所有 $b_i$ 互不相同。
尽管他的朋友们行动敏捷，他还是担心行动路径交叉的两个小朋友在过马路时发生碰撞。
皮皮认为，如果一个小朋友的行动路径没有跟其他任何小朋友的行动路径相交，则该小朋友是安全的。
请帮助皮皮计算安全的小朋友的数量。

2.2 分析

善用前缀信息和后缀信息。

2.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,ans,pfx_mx[MAXN],sfx_mn[MAXN];
struct Node{int a,b;bool operator<(const Node&rhs)const{return a<rhs.a;}
}p[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b;sort(p+1,p+n+1);pfx_mx[0]=-1e9,sfx_mn[n+1]=1e9;for(int i=1;i<=n;i++)pfx_mx[i]=max(pfx_mx[i-1],p[i].b);for(int i=n;i>=1;i--)sfx_mn[i]=min(sfx_mn[i+1],p[i].b);for(int i=1;i<=n;i++)if(p[i].b==pfx_mx[i]&&p[i].b==sfx_mn[i])ans++;cout<<ans;return 0;
}

3. 吃豆子

3.1 审题

现在有一个 $n\times m$ 的棋盘，左下角的格子为 $(1,1)$，右上角格子为 $(n,m)$，每个棋盘格子可以放任意数量的豆子。
小明有 $k$ 次操作，对于每次操作给出四个数字 $x_1,y_1,x_2,y_2$，表示小明会将所有 $(x,y)$ 满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 格子放上一个豆子。
在小明完成 $k$ 次操作后，他将对你进行 $q$ 次询问。
每次询问给出四个数 $x_1,y_1,x_2,y_2$，问所有 $(x_1,y_1)$ 满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 的格子上的豆子的总数和为多少？

3.2 分析

区间和模板，但是会超时：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2008;
const int MAXM=2008;
int n,m,k,q,a[MAXN][MAXM],pfx[MAXN][MAXM];
int main() {cin>>n>>m>>k>>q;for(int i=1,x1,y1,x2,y2;i<=k;i++){cin>>x1>>y1>>x2>>y2;for(int j=x1;j<=x2;j++)for(int k=y1;k<=y2;k++)a[j][k]++;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)pfx[i][j]=pfx[i-1][j]+pfx[i][j-1]-pfx[i-1][j-1]+a[i][j];for(int i=1,x1,y1,x2,y2;i<=q;i++){cin>>x1>>y1>>x2>>y2;cout<<pfx[x2][y2]-pfx[x1-1][y2]-pfx[x2][y1-1]+pfx[x1-1][y1-1]<<endl;}return 0;
}

所以需要用二维差分和二维前缀和，两者之间互相转换。

3.3 参考答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2008;
const int MAXM=2008;
int n,m,k,q,diff[MAXN][MAXM],a[MAXN][MAXM],pfx[MAXN][MAXM];
signed main(){cin>>n>>m>>k>>q;for(int i=1,x1,y1,x2,y2;i<=k;i++){cin>>x1>>y1>>x2>>y2;diff[x1][y1]++;diff[x1][y2+1]--;diff[x2+1][y1]--;diff[x2+1][y2+1]++;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){a[i][j]=diff[i][j]+(i>1?a[i-1][j]:0)+(j>1?a[i][j-1]:0)-(i>1&&j>1?a[i-1][j-1]:0);pfx[i][j]=a[i][j]+(i>1?pfx[i-1][j]:0)+(j>1?pfx[i][j-1]:0)-(i>1&&j>1?pfx[i-1][j-1]:0);}for(int i=1,x1,y1,x2,y2;i<=q;i++){cin>>x1>>y1>>x2>>y2;int result=pfx[x2][y2]-(x1>1?pfx[x1-1][y2]:0)-(y1>1?pfx[x2][y1-1]:0)+(x1>1&&y1>1?pfx[x1-1][y1-1]:0);cout<<result<<endl;}return 0;
}

三、高阶应用

1. 老式录音机

1.1 审题

小明要用录像机录 $N$ 个电视节目。 一共有 $C$ 个电视频道，从 $1$ 到 $C$ 编号。
第 $i$ 个电视节目从时刻 $s_i$ 开始，时刻 $t_i$ 结束，在频道 $c_i$ 播出。(包含开始时刻 $s_i$，不包含结束时刻 $t_i$)
同一个频道不会同时播出多个节目。
如果某个录像机在时刻 $S$ 到时刻 $T$ 录像某个频道的节目，如果接下来想用它录像其他频道的节目，需要将这个录像机接到另一个频道上，操作时间为 $D$，所以最早必须等到 $T+D$ 时刻才能开始录制其他频道的节目。
若要录下全部 $N$ 个节目，至少需要多少台录像机？

1.2 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int MAXT=2e6+8;
int n,c,d,maxt=0,diff[MAXT];
struct show{int s,t,c;bool operator<(show&rhs)const{if(c!=rhs.c)return c<rhs.c;else return s<rhs.s;}
}s[MAXN];
int main(){cin>>n>>c>>d;for(int i=1;i<=n;i++){cin>>s[i].s>>s[i].t>>s[i].c;maxt=max(maxt,s[i].t);}sort(s+1,s+n+1);for(int i=1;i<=n;i++){if(s[i].c==s[i-1].c&&s[i-1].t+d>s[i].s){diff[s[i-1].t+d]++;diff[s[i].t+d]--;}else{diff[s[i].s]++;diff[s[i].t+d]--;}}int ans=0,cnt=0;for(int i=1;i<=maxt;i++)cnt+=diff[i],ans=max(ans,cnt);cout<<ans;return 0;
}

2. [NOIP2012 提高组] 借教室

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+8;
int n,m,d[MAXN],s[MAXN],t[MAXN],base[MAXN],diff[MAXN];
bool check(int ans){for(int i=1;i<=n;i++)diff[i]=base[i];for(int i=1;i<=ans;i++)diff[s[i]]-=d[i],diff[t[i]+1]+=d[i];int rmn=0;for(int i=1;i<=n;i++){rmn+=diff[i];if(rmn<0)return false;}return true;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>base[i];for(int i=n;i>=1;i--)base[i]-=base[i-1];for(int i=1;i<=m;i++)cin>>d[i]>>s[i]>>t[i];if(check(m))return cout<<0<<endl,0;int l=0,r=m;while(l<r){int mid=l+(r-l>>1);if(check(mid))l=mid+1;else r=mid;}cout<<-1<<endl<<l;return 0;
}