前缀和与差分 PAT题目,差分个前缀和

前缀和与差分

1.前缀和：
前缀和是一种预处理，即给出n个数和m组访问，如果直接每次都在这些数列上操作，会造成超时，前缀和直接对这些访问进行预处理，最后直接得出取出结果进行计算。即O(n+m)。
相关题目：1046 Shortest Distance
AC代码：

#include<iostream>#include<algorithm>#include<string>#include<cmath>#include<cstring>#include<queue>#define N 100005using namespace std;int s[N]={0};int main(){ int n,m,a[N]={0},x,y; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; cin>>m; while(m--){ int sum=0,sum1=0; cin>>x>>y; if(x>y) swap(x,y); sum=s[y-1]-s[x-1]; sum1=s[n]-s[y-1]+s[x-1]; sum=min(sum1,sum); cout<<sum<<endl; } return 0;}

2.差分：
首先,给出一个问题:
给出n个数，再给出Q个询问，每个询问给出le，ri，x，要求你在le到ri上每一个值都加上x，而只给你O(n)的时间范围，怎么办？
思考一下:

如果暴力，卡一下le和ri，随随便便让你O(n^2)T成狗。
用线段树或树状数组搞一搞,抱歉,这个复杂度是O(Qlogn)的,还是会T(虽然他们解决别的题目很NB)
差分,没错,就是标题，很高兴O(n)+常数…
方法
还是用上面这个题目,假如要在le和ri上全都加一个x,很显然,这个O(n)是不可避免的,既然这样,那我们考虑把O(n*Q)变成O(n+Q).也就是说,在询问中我们不去for来加x,而是做一个标记,最后一起加上。嗯，这里暂时记住就好…
现在需要自己动笔模拟一下了！

实现
先另外开一个专门差分的数组(大小=题中的序列长度)

假如在3~8的区间上加上5,那我们在差分数组中的3位置上加上一个5(原因暂时不懂没关系,用笔先跟着模拟),再在8+1的位置上减一个5,如此操作完Q次。

假如我们只有这一次操作,开始统计答案,运用前置和的思想,cfi=cf[i-1]+cf[i].那么你会发现(如果你模拟了的话),在3~8的区间上,你已经使差分数组全部加上了5(推广到所有Q一起统计答案依旧正确)

再用O(n)的for把他们加到原序列之中去,输出!

看一下复杂度,果然:O(常数*n).

自拟题目设计代码：
下面还有一道板子题哦！！！

#include<iostream>#include<algorithm>#include<string>#include<cmath>#include<cstring>#include<queue>#define N 100005using namespace std;int cf[N]={0};int main(){ int n,m,a[N]={0}; int x,y,z; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>m; while(m--){ cin>>x>>y>>z; cf[x]+=z; cf[y+1]-=z; } for(int i=1;i<=n;i++){ cf[i]=cf[i-1]+cf[i]; a[i]+=cf[i]; cout<<a[i]<<' '; } cout<<endl; return 0;}

测试结果如下：

案例中给出5个数的数列，进行了3次操作，每次操作一个范围。

下面给出一道例题：
牛客北京信息科技大学第十一届程序设计竞赛（重现赛）：andy种树
这就是一道标准的差分问题，也可以说是模板了。

题目描述：
链接：https://ac.nowcoder.com/acm/contest/940/I
来源：牛客网

题目描述
andy在他的庄园里种了n棵树，排列成一排，标号为1到n。最开始的时候n棵树的高度都是0，也就是种子刚刚被埋下，树还没有长出来。

andy会一种魔法，他每使用一次魔法，就可以让树标号落在连续区间[l, r]里的树的高度增加1。他可以使用q次这种魔法，然后他很好奇，在使用了q次魔法之后，他的所有树的高度分别是多少呢？

输入描述:
第一行输入两个整数n，q。(1<= n, q <= 1e5)

接下来q行，每行输入两个整数l, r(l <= r)，表示andy让标号落在区间[l, r]里的数高度都加1
输出描述:
输出有一行n个整数，每个整数后面有空格。输出末尾没有换行

第i个数表示第i棵树的高度
示例1
输入
复制
10 3
1 3
2 4
3 3
输出
复制
1 2 3 1 0 0 0 0 0 0
说明
andy种了10棵树

第一次使用魔法使得1、2、3棵树的高度增加1,

所有树的高度为

1 1 1 0 0 0 0 0 0 0

第二次使用魔法使得2、3、4棵树的高度增加1，

所有树的高度为

1 2 2 1 0 0 0 0 0 0

第三次使用魔法使得第3棵树的高度增加1

所有树的高度为

1 2 3 1 0 0 0 0 0 0

代码展示：

#include<stdio.h>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<cmath>#include<queue>using namespace std;#define N 10001#define maxn 100005const int inf=0x3f3f3f3f;const int p=109;typedef long long ll;int main(){int n,q,f[maxn]={0},l,r;cin>>n>>q;while(q--){scanf("%d%d",&l,&r);f[l]++;f[r+1]--;}for(int i=1;i<=n;i++) f[i]=f[i]+f[i-1];for(int i=1;i<=n;i++) printf("%d ",f[i]);return 0;}