本文主要是介绍hdu 1166_线段树树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题之前用线段树做过，不过这周开始树状数组的学习，就用树状数组重新写了一遍。与线段树相比，树状数组在单个点更新和区间求和方面更有优势。另外代码也很简洁。
线段树AC代码：
#include <cstdiO>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
using namespace std;
const int p=50005;
int N,sum[p<<2],T;
int all;
void build(int k,int l,int r)
{sum[k]=0;if(l==r){scanf("%d",&sum[k]);return;}int m=(l+r)/2;build(lson);build(rson);sum[k]=sum[k<<1]+sum[k<<1|1];
}
int query(int k, int l, int r,int x, int y)
{if(x<=l&&r<=y)return sum[k];int m=(l+r)/2,all=0;if(x<=m) all+=query(lson,x,y);if(y>m) all+=query(rson,x,y);return all;
}void update(int k,int l,int r,int point,int add)
{if(l==r){sum[k]+=add;return;}int m=(l+r)/2;if(point<=m){update(lson,point,add);sum[k]=sum[k<<1]+sum[k<<1|1];}else{update(rson,point,add);sum[k]=sum[k<<1]+sum[k<<1|1];}
}
int main()
{int x,y,cas=0;char ch[8];scanf("%d",&T);while(T--){scanf ( "%d" , &N ) ;printf("Case %d:\n",++cas);build(1,1,N);while(scanf("%s",ch),strcmp(ch,"End")!=0){all=0;scanf("%d%d",&x,&y);if(!strcmp(ch,"Query")){// query(1,1,N,x,y);//printf("%d\n",all);printf("%d\n",query(1,1,N,x,y));}else{if(!strcmp(ch,"Sub"))y=-y;update(1,1,N,x,y);}}}
}树状数组AC代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int p = 50005;
int C[p],sum[p],a[p];
int n;
int lowbit(int k)
{return k&(-k);
}
void build(int k)
{for(int i = 1;i <= k; i++){C[i] = sum[i] - sum[i-lowbit(i)];}/*cout<<"TEST"<<endl;for(int i = 1;i <= k; i++)printf("%d ",C[i]);*/
}
int query(int i,int j)
{int sum1,sum2;sum1 = sum2 = 0;while(i>0){sum1 += C[i];i -= lowbit(i);}while(j>0){sum2 += C[j];j -= lowbit(j);}return sum2-sum1;
}
void update(int pos,int val)
{a[pos] += val;while(pos<=n){C[pos] += val;pos += lowbit(pos);}
}int main()
{int T,cas;scanf("%d",&T);cas = 0;char str[20];//string str;int i, j;while(T--){//memset(C,0,sizeof(C));scanf("%d",&n);printf("Case %d:\n",++cas);a[0]=0;for(i = 1;i <= n; i++){scanf("%d",&a[i]);sum[i] = sum[i-1] +a[i];}build(n);while(1){scanf("%s",&str);//cin>>str;//cout<<str<<endl;if(!strcmp(str,"End"))break;elsescanf("%d%d",&i,&j);if(!strcmp(str,"Query"))printf("%d\n",query(i-1,j));else if(!strcmp(str,"Add"))update(i,j);else if(!strcmp(str,"Sub"))update(i,-j);}}return 0;
}
这篇关于hdu 1166_线段树树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
