log(n)修改,log(n)查询
可以顶替掉一部分线段树的作用,而且码量十分友好
但是对我来说是有点难理解的,现在只是大体理解,没有很通透,所以不写自己的理解了,以后要多看看
1.单点修改区间查询
https://blog.csdn.net/ls2868916989/article/details/119268741
代码(P3374):
#include<iostream> #include<cstdio> using namespace std; const long long N=1e6+10; int n,m,u,v,w,a[N]; int c[N]; int lowbit(int x){ return x&(-x); } void change(int x,int y){ while(x<=n){ c[x]+=y; x+=lowbit(x); } } int print(int x){ int cnt=0; while(x>0){ cnt+=c[x]; x-=lowbit(x); } return cnt; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ int h=i; while(h<=n){ c[h]+=a[i]; h+=lowbit(h); } } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); if(u==1) change(v,w); else printf("%d\n",print(w)-print(v-1)); } return 0; }
2.区间修改单点查询
去看这篇博客!!写的超级无敌好 https://www.cnblogs.com/daybreaking/p/9408301.html
大概的意思就是搞一个差分数组,修改的时候直接头尾一加一减,单点查询的时候要逐个相加
代码(P3374):
#include<iostream> #include<cstdio> using namespace std; const long long N=1e6+10; int n,m,a[N],d[N]; int c[N],k,u,v,w; int lowbit(int x){ return x&(-x); } void change(int x,int y){ while(x<=n){ c[x]+=y; x+=lowbit(x); } } int print(int x){ int cnt=0; while(x>0){ cnt+=c[x]; x-=lowbit(x); } return cnt; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); d[i]=a[i]-a[i-1]; } for(int i=1;i<=n;i++){ int h=i; while(h<=n){ c[h]+=d[i]; h+=lowbit(h); } } for(int i=1;i<=m;i++){ scanf("%d",&k); if(k==1){ scanf("%d%d%d",&u,&v,&w); change(u,w); change(v+1,-w); } else{ scanf("%d",&u); printf("%d\n",print(u)); } } return 0; }
标签:cnt,return,树状,int,lowbit,long,数组,include From: https://www.cnblogs.com/dgdger/p/17603110.html