欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

寒假集训之树状数组

程序员文章站 2024-03-20 13:51:34
...

自学链接
模板题:HDU1166

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int tree[maxn+10];
int a[maxn+10];
int n;
inline int lowbit(int x)
{
    return (x&-x);
}
void add(int x,int value)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=value;
}
long long get(int x)
{
    long long sum=0;
    for(int i=x;i;i-=lowbit(i))
        sum+=tree[i];
    return sum;
}
int main()
{
   int t;cin>>t;
   int tmp=t;
   while(t--)
   {
       printf("Case %d:\n",tmp-t);
       scanf("%d",&n);
       memset(tree,0,sizeof tree);
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&a[i]);
           add(i,a[i]);
       }
        char s[10];
        int i,j;
        while(scanf("%s",s)&&strcmp(s,"End")!=0)
        {
            scanf("%d%d",&i,&j);
            if(strcmp(s,"Query")==0)
                printf("%lld\n",get(j)-get(i-1));//查询区间之和用减法就好
            else if(strcmp(s,"Add")==0)
                add(i,j);
            else if(strcmp(s,"Sub")==0)
                add(i,-1*j);//某个点减少了,用加负数
        }
   }
   return 0;
}