树状数组
发布时间:2020-12-14 03:20:19 所属栏目:大数据 来源:网络整理
导读:目录 一维树状数组 单点更改,区间求和 区间修改,单点求值 高级应用:区间修改区间求值 二维树状数组 一维树状数组 单点更改,区间求和 回到顶部 #include iostream #define MX 500010#define lowbit(x) (x(-x)) using namespace std;int n;int c[1000],a[1
目录
一维树状数组单点更改,区间求和回到顶部 #include <iostream> #define MX 500010 #define lowbit(x) (x&(-x)) using namespace std; int n; int c[1000],a[1000]; void add(int x,int y){//对于节点x加上y for(;x<=n;x+=(lowbit(x))){ c[x]+=y; } } int sum(int x){//计算1..x的求和,类似于前缀和 int ans=0; for(;x>=1;x-=lowbit(x)){ ans+=c[x]; } return ans; } int query(int left,int right){//区间查询,就是利用前缀和的思想 return sum(right)-sum(left-1); } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; update(i,a[i]); } int l,r; while(1){ cin>>l>>r; cout<<query(l,r); } } 区间修改,单点求值回到顶部 #include <iostream> #define MX 500010 #define lowbit(x) (x&(-x)) using namespace std; int n,m,a[1000],c[1000]; void add(int x,int k){ for(;x<=n;x+=lowbit(x)){ c[x]+=k; }; } int sum(int x){ int ans=0; for(x;x>=1;x-=lowbit(x)){ ans+=c[x]; } return ans; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int q,w,e; for(int i=1;i<=m;i++){ cin>>q; if(q==1){ cin>>q>>w>>e; add(q,e); add(w+1,-e); }else{ cin>>q; cout<<a[q]+sum(q)<<endl; } } } 高级应用:区间修改&区间求值如图,上面是线段树,下面是树状数组。 在区间加法和查询明显代码量以及时空效率都优于线段树。 当然如果要支持最大最小什么的可能只能用线段树了。 #include <iostream> #define lowbit(x) (x&(-x)) #define MX 100010 #define LL long long using namespace std; LL n,q,c1[MX],c2[MX],a[MX]; void add(LL *r,LL x,LL k){//采用LL *r传递每次要修改的数组 for(;x<=n;x+=lowbit(x)){ r[x]+=k; } } LL sum(LL *r,LL x){ LL ans=0; for(;x>=1;x-=lowbit(x)){ ans+=r[x]; } return ans; } int main() { LL sum1,sum2; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; add(c1,i,a[i]-a[i-1]); add(c2,(i-1)*(a[i]-a[i-1])); } int q,l,r,k; for(int i=1;i<=m;i++){ cin>>q; if(q==1){ cin>>l>>r>>k; add(c1,k); add(c1,r+1,-k); add(c2,(l-1)*k); add(c2,-r*k); }else{ cin>>l>>r; sum1=(l-1)*sum(c1,l-1)-sum(c2,l-1); sum2=r*sum(c1,r)-sum(c2,r); cout<<(sum2-sum1)<<endl; } } return 0; } 二维树状数组等待填坑 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |