调查数组差分配序列通过维持相邻要素的差分值，实现多次区间操作的优化。 (第一次) ) )。
例如，假设多次操作a、b、c，使[a、b]内元素全部为c . 然后求出各元素值
如果是普通的暴力求法，每次对[a，b]来说复杂度都太高了。 所以我们有优化的技术。 穿有差别的排列。 c[I]=a[I]a[I1](I=2) c [ I ]=a [ I-1 ] ) I=2) c[1]=
这样，我们发现的a[i]式
a [ I ]=c [1] c [2] . c [ I ] a [ I ]=c [1] c [2] . c [1] c [2] . c [ I ]复杂度o[1]
参考资料：这个大人物的博客
3359 www.cn blogs.com/Colin-lightning/p/8436624.html
# include iostream # include cstdio # include cmath # include cstring # includealgorithmusingnamespacestd； int d[100010]，a[100010]，l，r； int main () { int n； while(scanf('%d '，n )，n ) { memset(d ) d，0，sizeof(d ) }； 短信(a，0，sizeof(a ) a )； for(intI=1； i=n； I ) { sca
nf("%d%d",&l,&r); d[l]+=1; d[r+1]-=1; } for(int i=1;i<=n;++i) a[i]=a[i-1]+d[i]; for(int i=1;i<n;++i) printf("%d ",a[i]); printf("%dn",a[n]); } return 0;}
题目
https://www.luogu.org/problem/P1083
题意：中文题意，给定一个序列，进行多次区间修改，输出第一次区间修改不能执行的序号（比方说已经删除成0 了，不可再删除了）
思路：二分+差分数组。 O(logn*n)
#include <iostream>#include <cstdio>#include <cstring>using namespace std;/* 用差分数组，O1处理，然后判断让谁 修改的时候二分答案一下。*/const int maxn=1e6+500;typedef long long ll;int a[maxn];int b[maxn];int c[maxn];ll num[maxn];ll cf[maxn];int m;bool judge(int p){ memset(cf,0,sizeof(cf)); for(int i=1;i<=p;i++){ cf[b[i]]+=1ll*a[i]; cf[c[i]+1]-=1ll*a[i]; } for(int i=1;i<=m;i++){ cf[i]+=cf[i-1]; //cout<<cf[i]<<"*"<<i<<" "<<p<<endl; if(cf[i]>num[i])return true; } return false;}int main(){ int n; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++){ scanf("%lld",&num[i]); } for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i],&b[i],&c[i]); } if(!judge(n)){ puts("0");return 0; } puts("-1"); int r=n*2; int l=0; int ans=-1; while(l<r){ int mid=(l+r)>>1; if(judge(mid)){ r=mid; ans=mid; } else{ l=mid+1; } } printf("%dn",ans); return 0;} 树状数组的区间修改
关于树状数组，我知道他是一个非常巧妙的利用计算机存储数字的特性得到的类似一种固态二分的写法。利用线段树进行点更新，区间查询，异常简单。但是区间修改呢（线段树的lazy区间修改也很巧妙）。
我们已经知道了利用差分数组来求多次修改后的a[i]$$
ans = a[1] + a[2] + a[3] +……+ a[q-1] + a[q] sum=sigma(c,1) + sigma(c,2) + sigma(c,3) +…… + sigma(c, q-1 ) + sigma(c, q ) =c[1] + ( c[1] + c[2] ) + ( c[1] + c[2] + c[3] ) + …… + （c[1] + c[2]+……+ c[q-1] )+ ( c[1] + c[2]+……+ c[q] ) = q*c[1] + (q-1)*c[2] + (q-2)*c[3] +…… + c[q] = ｑ* (c[1]+c[2]+...+c[ｑ]) - (0*c[1]+1*c[2]+...+(ｑ-1)*c[ｑ]) =(q+1) *(c[1]+c[2]+...+c[q])-(1*c[1]+2*c[2]+...+q*c[q])
所以我们需要维护两个树状数组 一个是正常的查分数组。另一个是i*w(w为修改项),修改四次，虽然修改的次数多了两次，但是代码非常好写。
证明过程是这个大佬的源出处 https://blog.csdn.net/weixin_42557561/article/details/81781916
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int maxn=200005,maxq=200005;int n,q;int lowbit(int x){ return x&(-x);}long long delta[maxn]; //差分数组long long deltai[maxn]; //delta*ilong long sum[maxn];//原始前缀和void update(long long *c,int x,int y){ while(x<=n) { c[x]+=y; x+=lowbit(x); }}long long query(long long *c,int x){ long long ans=0; while(x>0) { ans+=c[x]; x-=lowbit(x); } return ans;}int x[maxn];int main(){ cin>>n>>q; for(int i=1;i<=n;i++) { //int x; cin>>x[i]; //sum[i]=sum[i-1]+x; } for(int i=1;i<=n;i++){ update(delta,i,x[i]-x[i-1]); update(deltai,i,(x[i]-x[i-1])*i); } while(q--) { int x; cin>>x; if(x==1) { int y,z,w; cin>>y>>z>>w; update(delta,y,w); update(delta,z+1,-w); update(deltai,y,w*y); update(deltai,z+1,-w*(z+1)); } if(x==2) { int y,z; cin>>y>>z; long long suml=(z+1)*query(delta,z)-query(deltai,z); suml-=y*query(delta,y-1)-query(deltai,y-1); cout<<suml<<endl; } } return 0;}
记：那俩示例代码都是扒的emm，以后碰见相关思路的题目我在补到这上面吧。我第一次看见查分数组这种操作还以为是codeforces的骚操作（毕竟codeforces上有很多我不理解的数学证明（智力碾压）的结论）没想到基本的思想竟然和我最喜欢的BIT有关。