hdu1166(树状数组)

本文主要是介绍hdu1166(树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1166

思路
理解树状数组后直接可以套模板

#include<iostream>
#include<cstdio>
using namespace std;template<class T>
class Binary_Index_Tree{
public:T * a;T * c;int size;Binary_Index_Tree(T * b,int size){if(b==NULL) return;a=new T[size+1];c=new T[size+1];this->size=size+1;//init for(int i=0;i<size+1;i++){a[i]=0;c[i]=0;}//build for(int i=1;i<=size;i++){a[i]=b[i-1];add(i, a[i]);}}//以0起始 T sum(int i){i++;T sum=0;while(i>=1){sum += c[i];i-=lowbit(i);}return sum;}T query(int l,int r){T res= sum(r)-sum(l)+a[l+1];return res;}T get(int i){return a[i+1];}T set(int i,T v){i++;T d=v-a[i];a[i] = v;add(i,d);}private:int lowbit (int x){return x&(-x);} ;void add(int i,T v){while(i>=1&&i<this->size){c[i]+=v;i+=lowbit(i);}}};int b[50005];
int main()
{int T;scanf("%d",&T);int cas=1;while(T--){int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&b[i]);printf("Case %d:\n",cas++);int *t =b;Binary_Index_Tree<int>tree(t,n); char str[40];scanf("%s",str);while(str[0]!='E'){int x,y;scanf("%d %d",&x,&y);if(str[0]=='A')tree.set(x-1,tree.get(x-1)+y);if(str[0]=='S')tree.set(x-1,tree.get(x-1)-y);if(str[0]=='Q'){int re=tree.query(x-1,y-1);printf("%d\n",re);}scanf("%s",str);}   }
}

这篇关于hdu1166(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---