本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，~~主要是因为我三本都买了~~ 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（~~习题和代码可全都是我自己敲哒~~）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。

下方链接为学习笔记目录链接（中转站）

一、前缀和

给定一个序列，定义 $p r e [i] = p r e [i - 1] + a [i]$

可求区间[l,r]的和： $p r e [r] - p r e [l - 1]$

可求区间的[l,r]的异或和：（异或的逆运算是它本身）所以即为pre[r]^ pre[l-1]

二、二维前缀和

二维的前缀和根据容斥原理推导得到的

定义： $p r e [i] [j] = p r e [i - 1] [j] + p r e [i] [j - 1] - p r e [i - 1] [j - 1] + a [i] [j] ， p r e [i] [j]$ 表示的是 $(i, j)$ 左下角的一个子矩形

如下图：很容易就能得到上述的定义公式

1.二维前缀和的修改和求和

如果要使区间 $x_{1} < = x < = x_{2}$ ， $y_{1} < = y < = y_{2}$ 里的数全部+1那么需要进行下面的操作（利用差分思想）:

void add(ll x_1,ll y_1,ll x_2,ll y_2)
{
    a[x_1][y_1]++;
    a[x_2+1][y_2+1]++;
    a[x_1][y_2+1]--;
    a[x_2+1][y_1]--;
}

注意运用前缀和修改矩阵以后要先求一遍前缀和还原原矩阵，然后再求一遍前缀和才是真正的前缀和，这样才能继续进行下一步的操作
具体实例见下见下面的例题模板：牛妹吃豆子

0. NOI 2003激光炸弹（二维前缀和）

输入样例：

2 1
0 0 1
1 1 1

输出样例：

这里用到了二维前缀和。
本题种有几点需要注意：

1.我们把 $(x i, y i) (x i, y i)$ 作为一个格子,但是实际上他们只是一个点,所以说我们不妨认为这个点就是这个格子的中心,既然如此的话我们就可以认为是 $(x i - 0.5, y i - 0.5)$
2. 本题中的空间给的很小，只有125MB，所以计算前缀和的时候就不用开两个数组了，直接用一个数组来算就好，反正前缀和只与前面的状态有关，当前的状态无关。
3. 因为题目要求边上的目标是不能炸到的，所以这里实际上是求r-1的前缀和，回到代码里就是 $i - r$ ，不然应该写 $i - r - 1$
4. 然后剩下的就是基本的前缀和操作了，取范围为r 的前缀和即可

#include<iostream>
#include<string.h>
#include<cstdio>
#include<math.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef int ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=5002;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0

ll n,m,r;
ll s[N][N];
int main()
{
    scanf("%d%d",&n,&r);
    while(n--)
    {
        ll x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        s[x+1][y+1]=val;
    }
    over(i,1,5001)over(j,1,5001)
    {
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
    }
    ll ans=0;
    over(i,0,5001-r)over(j,0,5001-r)
    {
        ll sum=s[i+r][j+r]-s[i+r][j]-s[i][j+r]+s[i][j];
        ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}

1.牛妹吃豆子（二维前缀和模板，修改+求和）

题目链接：https://ac.nowcoder.com/acm/contest/5158/D

注意运用前缀和修改矩阵以后要先求一遍前缀和还原原矩阵，然后再求一遍前缀和才是真正的前缀和

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=2005;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

ll n,m,a[N][N];

void add(ll x_1,ll y_1,ll x_2,ll y_2)
{
    a[x_1][y_1]++;
    a[x_2+1][y_2+1]++;
    a[x_1][y_2+1]--;
    a[x_2+1][y_1]--;
}
ll k,q;
ll x_1,x_2,y_1,y_2;
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
    while(k--){
        scanf("%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2);
        add(x_1,y_1,x_2,y_2);
    }
    over(i,1,n)over(j,1,m)//求两次前缀和
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
    over(i,1,n)over(j,1,m)
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
    while(q--)
    {
        scanf("%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2);//求区间的和
        ll ans=a[x_2][y_2]+a[x_1-1][y_1-1]-a[x_1-1][y_2]-a[x_2][y_1-1];
        printf("%lld\n",ans);
    }
    return 0;
}

2.静态数组的区间求和问题

静态数组的区间求和问题

3.静态维护区间加等差数列的求和问题

静态维护区间加等差数列的求和问题

三、差分

对于一个给定的数列A，它的差分数列B定义为：
$B [1] = A [1], B [i] = A [i] - A [i - 1] (2 < = i < = n)$

前缀和与差分运算为互逆运算，任意一个数组A 的前缀和数组的差分数组是它本身。

让区间 $[l, r]$ 里的数均+k就是让原数列的差分数组a， $a [l] + = k; a [r + 1] - = k$ 然后 $f o r (i n t i = 1; i < = n; i + +) a [i] + = a [i - 1]$ 即可还原数组，所以千万注意修改区间之后要求一遍前缀和才能差分数组转换成修改过后的原数组，再进行各种操作。（~~应该不会有人像我这么菜忘了求原数组直接乱搞一通WA⑧，真的丢人，我得记一辈子~~ ）

具体的操作如下：

#include<iostream>
#include<string.h>
#include<cstdio>
#include<math.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=110000;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0

ll b[N];
ll n,m,a[N],pos,neg;
int main()
{
    scanf("%lld%lld",&n,&m);
    over(i,1,n)
        scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
    over(i,1,m){
        ll l,r,k;
        scanf("%lld%lld%lld",&l,&r,&k);
        b[l]+=k,b[r+1]-=k;
    }
    over(i,1,n)
        a[i]=a[i-1]+b[i],printf("%lld ",a[i]);
    return 0;
}

输入：

输出：

3 4 4 3 2

差分思想在很多地方应用很广，比如要求使一个数列中的数全部相同，就可以转化成使这个数列的差分数组全部为0。比如下面这道例题：

3.IncDec Sequence（增减序列）（差分+贪心）

链接：https://www.acwing.com/problem/content/description/102/

输出：

1
2

思路：
利用上面的性质，因为我们只要求A序列中所有的数相同，而不在意这些方案具体是什么，所以说我们就可以转化题目，也就是将对A序列的 $+ 1, - 1$ 操作，让A序列相同，改成目标把 $B_{2}, \dots, B_{n}$ 变成全0即可，也就是A序列全部相等。

利用差分的修改： $a [l] + = 1; a [r + 1] - = 1$ ，每一次选取一个Bi和Bj，（2<=i,j<=n）,而且这两个数，一个为正数，一个为负数，至于为什么要是正负配对，因为我们是要这个B序列2~n都要为0，所以这样负数增加，正数减少，就可以最快地到达目标为0的状态。

至于那些无法配对的数Bk可以选B1或者Bn+1，这两个不影响的数，进行修改。

所以说我们这道题目得出的答案就是，最少操作数 $m i n (p o s, n e g) + a b s (p o s - n e g) = m a x (p o s, n e g)$ ，然后最终序列a可能会有 $a b s (p o s - n e g) + 1$ 种情况。

~~positive 正数 negative 负数~~

#include<iostream>
#include<string.h>
#include<cstdio>
#include<math.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=110000;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0


ll n,m,a[N],p,q;
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
        scanf("%lld",&a[i]);
    over(i,2,n){
        ll c=a[i]-a[i-1];
        if(c>0)p+=c;
        else q-=c;
    }
    printf("%lld\n%lld\n",max(p,q),abs(p-q)+1);
    return 0;
}

https://www.luogu.com.cn/problem/P2879

输入：

输出：

题目中给我们m对关系，实际上是告诉我们a和b之间的所有的牛都比a，b 矮，而题目中要求的是所有的牛高度的最大值，所以利用差分的思想，标记从a+1到b-1之间的都-1，也就是 A[a+1]--,A[b]++;，因为第p头牛一定是最高的，所以A[p]=0但是因为输入的数据一定合法所以这个可以忽略不计。这样每头牛的高度都是A[i]+h，利用差分的思想 $O (m + n)$ 的时间复杂度下修改即可。
还有一点非常坑爹的就是数据中的a，b可能会重复多次输入~~不愧是USAOC的毒瘤题，输入输出是真的狠~~，所以要判重，这里直接开一个map，因为如果直接开bool数组可能会爆内存。还有就是a可能大于b，所以要先判断。每次写题前先把数据处理好是一个好习惯，虽然一般的比赛的数据都不会这么毒瘤，但是谁又说得准呢，小心点没毛病

#include<iostream>
#include<string.h>
#include<cstdio>
#include<math.h>
#include<map>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,全部换成int看会不会A，别动这里！！！
const ll N=110000;
const ll mod=1e9+7;
const double EPS=1e-10;//-10次方约等于趋近为0

int n,m,h,p;
map<pair<int,int>,bool>existed;
ll A[N],B[N];
int main()
{
    cin>>n>>p>>h>>m;
    over(i,1,m){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(a>b)swap(a,b);
        if(existed[make_pair(a,b)])continue;
        A[a+1]--,A[b]++;
        existed[make_pair(a,b)]=true;
    }
    over(i,1,n)
    {
        B[i]=B[i-1]+A[i];
        printf("%lld\n",B[i]+h);
    }
    return 0;
}

5.P3406 海底高铁（差分，前缀和，贪心)

P3406 海底高铁
题目背景
大东亚海底隧道连接着厦门、新北、博艾、那霸、鹿儿岛等城市，横穿东海，耗资1000亿博艾元，历时15年，于公元2058年建成。凭借该隧道，从厦门可以乘坐火车直达台湾、博艾和日本，全程只需要4个小时。
题目描述
该铁路经过N个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第i段铁路连接了城市i和城市i+1(1<=i<N)。如果搭乘的比较远，需要购买多张车票。第i段铁路购买纸质单程票需要Ai博艾元。
虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了IC卡。对于第i段铁路，需要花Ci博艾元的工本费购买一张IC卡，然后乘坐这段铁路一次就只要Bi(Bi<Ai)元。IC卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第i段铁路的IC卡，无法乘坐别的铁路的车。
Uim现在需要出差，要去M个城市，从城市P1出发分别按照P1,P2,P3…PM的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。
输入格式
第一行两个整数，N，M。接下来一行，M个数字，表示Pi接下来N-1行，表示第i段铁路的Ai,Bi,Ci。
输出格式
一个整数，表示最少花费。
KKK的思路：对于其中一小段，我们要么全部买纸票，要么全部刷卡。
所以我们只需要统计每一小段经过的总次数。
如果你暴力模拟统计的话，估计会tle。
怎么快速知道每一段次数呢？
我们回忆一下“借教室”这道题。
如果你高兴的话，可以上线段树或者树装数组——但是没必要。
假设有5段，我们把1到3加上1，可以像图2一样，开头+1，结尾-1。然后2到4加1，如图3.

                  +1      -1          +1 +1   -1 -1
 - - - - -        --  - - -- -        -- -- - -- --
 1 2 3 4 5        1   2 3 4  5        1  2  3 4  5
 图1                   图2               图3

然后呢，我们求出每一项前缀和（就是从前往后加）：

然后每一段直接贪心比较，然后就没有然后了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
ll n,m,ans,a[maxn],b[maxn],c[maxn],x,y,t[maxn],d[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>d[i];
    for(int i=1;i<=n-1;i++)
        cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=m-1;i++)
    {
        x=min(d[i+1],d[i]);//左端点和右端点
        y=max(d[i+1],d[i]);
        t[x]++;
        t[y]--;//从1到4是经过了123，所以y已经是右端点+1了
    }
    for(int i=1;i<=n;i++)//前缀和
        t[i]+=t[i-1];
    for(int i=1;i<=n-1;i++)
        ans+=min(a[i]*t[i],b[i]*t[i]+c[i]);//贪心求最小花费
    cout<<ans<<endl;
    return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧

0x03.基本算法—前缀和与差分

目录