目录
一.前缀和
给定一个序列，定义pre[i]=pre[i-1]+a[i];
可求区间[l,r]的和：pre[r]-pre[l-1];
可求区间的[l,r]的异或和：（异或的逆运算是它本身）所以即为pre[r]^pre[l-1];
若有n组操作，操作为将区间[l,r]中的数增加k，最后输出这个数组。
可以暴力跑，但如果数据较大就会超时，所以要用到下面的差分思想。
二. 差分思想
差分：一个数列，如果知道第一个数，以及每一个数与前一个数的差值，那么我们就可以推出整个数列。先遍历一遍数组使a[i]=a[i]-a[i-1]；让区间[l,r]里的数均+k就是让a[l]+=k;a[r+1]-=k;然后for(int i=1;i<=n;i++) a[i]+=a[i-1];即可还原数组
对于一个数组a定义数组 s[i]=∑j=0ia[j]
a[j]为a数组的前缀和数组。
//为了避免数组越位，下标从1开始用
for(int i=1;i<=n;++i)
{
s[i]=s[i-1]+a[i];
}
定义数组 d[i]={a[i]a[i]−a[i−1] if i=0 if i≥1 为a数组的差分数组。
//为了避免数组越位，下标从1开始用
for(int i=n;i;--i) //倒着for的可以不借助两个数组，这里用d和a是为了看着清楚，实际可以用一个数组储存。
{
d[i]=a[i]-a[i-1];
}
前缀和与差分运算为互逆运算，任意一个数组a的前缀和数组的差分数组是它本身。
1.静态数组的区间求和问题
2.静态维护区间加等差数列的求和问题
三.二维前缀和
定义：pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
pre[i][j]表示的是(i,j)左下角的一个子矩形
类似容斥原理
二维前缀和例题P2280 [HNOI2003]激光炸弹
P2280 [HNOI2003]激光炸弹（二维前缀和的简单应用）难度⭐⭐⭐
四.例题
例题一：差分+前缀和+贪心
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
然后呢，我们求出每一项前缀和（就是从前往后加）：
1 2 2 1 0
- - - - -
1 2 3 4 5
图4
然后每一段直接贪心比较，然后就没有然后了
#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;
}
例题二.差分+前缀和
题目链接
题目描述
HJ养了很多花（99999999999999999999999999999999999盆），并且喜欢把它们排成一排，编号0~99999999999999999999999999999999998,每天HJ都会给他的花浇水，但是他很奇怪，他会浇n(1 <= n <= 2 * 105)次水，每次都会选择一个区间[l, r]，(0 <= l <= r <= 106),表示对区间[l, r]的花都浇一次水。现在问你，通过这些操作之后，被浇了i(1 <= i <= n)次水的花的盆数。
输入描述:
输入：第一行一个n，表示HJ的操作次数，接下来的n行，表示每一次选择的浇水区间。
输出描述:
输出：输出n个数字Cnt1, Cnt2……Cntn,（用空格隔开）Cnti表示被浇了i次水的花的盆数。
示例1
输入
30 31 33 8
输出
6 2 1
示例2
输入
31 32 45 7
输出
5 2 0
说明
对于样例1的图形解释被浇了1次的有:0, 4, 5, 6, 7, 8, cnt1 = 6
被浇了2次的有：1, 2. cnt2 = 2
被浇了3次的有: 3 . cnt3 = 3
思路：差分
等会再改
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll a[maxn],b[maxn],c[maxn],sum[maxn]；
int main()
{
int n;
while(cin>>n)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x]++,b[y+1]++;
}
ll a1=0,a2=0;
for(int i=0;i<=maxn;i++)
{
a1+=a[i];
a1-=b[i];
sum[a1]++;
}
for(int i=1;i<=n;i++) printf("%lld ",sum[i]);
puts("");
}
return 0;
}
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号