树状数组的基本用法（板子）

概述写这篇博客，为了方便自己后续复制粘贴板子；  HDU 1166 题意：单点查询，区间更新 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 6 #define lowbit(x) ((x)&-(x)) 7 typedef long long ll

写这篇博客，为了方便自己后续复制粘贴板子； 

HDU 1166

题意：单点查询，区间更新

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5  6 #define lowbit(x) ((x)&-(x)) 7 typedef long long ll; 8 const int maxn=5e5+5; 9 int n,q,a[maxn],c[maxn];10 11 voID add(int x,int val)12 {13     while(x<=n)14     {15         c[x]+=val;16         x+=lowbit(x);17     }18 }19 20 int ask(int x)21 {22     int ans=0;23     while(x>0)24     {25         ans+=c[x];26         x-=lowbit(x);27     }28     return ans;29 }30 31 int main()32 {33     //freopen("in.txt","r",stdin);34     //ios::sync_with_stdio(false);35     int T,kase=0; cin>>T;36     while(T--)37     {38         cin>>n;39         memset(c,0,sizeof(c));40         for(int i=1; i<=n; i++)41         {42             int x; cin>>x;43             add(i,x);44         }45 46         printf("Case %d:\n",++kase);47         char s[10];48         while(scanf("%s",s+1),s[1]!=‘E‘)49         {50             int x,y; cin>>x>>y;51             if(s[1]==‘Q‘)52                 printf("%d\n",ask(y)-ask(x-1));53             else if(s[1]==‘A‘)54                 add(x,y);55             else56                 add(x,-y);57         }58     }59     return 0;60 }

VIEw Code

 

POJ 3468 

题意：区间查询，区间更新； 

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5  6 #define lowbit(x) ((x)&-(x)) 7 #define _rep(x,y) for(int i=(x); i<=(y); i++) 8 typedef long long ll; 9 const int maxn=1e5+5;10 ll sum1[maxn],sum2[maxn],sum[maxn];11 int n,c[maxn];12 13 voID add(int x,int val)14 {15     int i=x;16     while(i<=n)17     {18         sum1[i]+=val;19         sum2[i]+=val*x;20         i+=lowbit(i);21     }22 }23 24 voID range_add(int l,int r,int x)25 {26     add(l,x); add(r+1,-x);27 }28 29 ll ask(int x)30 {31     ll ans=0; int i=x;32     while(i>0)33     {34         ans+=(x+1)*sum1[i]-sum2[i];35         i-=lowbit(i);36     }37     return ans;38 }39 40 ll range_ask(int l,int r)41 {42     return ask(r)-ask(l-1);43 }44 45 46 int main()47 {48     //freopen("in.txt",stdin); 49     ios::sync_with_stdio(false);50     cin>>n>>q;51     _rep(1,n){52         cin>>a[i];53         sum[i]=sum[i-1]+a[i];54     }55     while(q--)56     {57         char cmd; int x,y;58         cin>>cmd>>x>>y;59         if(cmd==‘Q‘)60             printf("%I64d\n",sum[y]-sum[x-1]+range_ask(x,y));61         else62         {63             int z; cin>>z;64             range_add(x,y,z);65         }66     }67     return 0;68 }

VIEw Code 总结

以上是内存溢出为你收集整理的树状数组的基本用法（板子）全部内容，希望文章能够帮你解决树状数组的基本用法（板子）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。