hdu 1166 树状数组解-白红宇

hdu 1166 树状数组解

阅读量：5135 次

发布时间：2019-06-13

本文共 1261 字，大约阅读时间需要 4 分钟。

树状数组解决（关于树状数组参考大佬的博客）

然后就很好理解这题了，代码附上

/*hdu 1166 单点修改，区间查询*/#include 
     
      #include 
      
       #include 
       
         #define MAX 50010using namespace std;int tree[MAX];int arr[MAX];int n;int lowbit(int x){    return x&(-x);} //初始化树状数组 void init (){   tree[0] = 0;  for (int i=1;i<=n;++i)   {         tree[i]= 0;         for (int j=i-lowbit(i)+1;j<=i;++j)         tree[i]+=arr[j];   }}//获取区间和 int get_sum(int x){  int ans = 0;  for (int i=x;i>0;i-=lowbit(i))     ans+=tree[i];     return ans;}//更新数据 int add(int x,int p){  for (int i=x;i<=n;i+=lowbit(i))    tree[i]+=p;}int main (){  char ch[10];  int T = 0;  int a,b;  cin>>T;  for (int k=1;k<=T;++k)  {   cin >> n;      for (int i=1;i<=n;++i)        scanf ("%d",&arr[i]);        init();//更新         printf ("Case %d:\n",k);      //开始查询等操作      while(~scanf ("%s",ch))      {             if (!strcmp("End",ch)) break;            scanf ("%d%d",&a,&b);           if (!strcmp("Query",ch))             printf ("%d\n",get_sum(b)-get_sum(a-1));           else if (!strcmp("Add",ch))                add(a,b);           else add(a,-b);      }   } return 0;}/*1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End */