线段树入门——区间求和，单点更新

佚名 6年前 (2019-04-23) 随笔 1388人围观抢沙发百度已收录

线段树入门区间求和，单点更新。

题目链接：https://cn.vjudge.net/problem/HDU-1166

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<cstdio>
#include<cstring>

const int maxn=50000;
const int maxsize=(1<<17)-1;
char s[10];

int data[maxsize];

void update(int v,int pos,int k,int l,int r)
{
    if(pos<l||pos>=r)
        return;
    data[k]+=v;
    if(r-l==1)
        return;
    update(v,pos,2*k+1,l,(l+r)/2);
    update(v,pos,2*k+2,(l+r)/2,r);
}

int query(int a,int b,int k,int l,int r)
{
    if(b<=l||a>=r)
        return 0;
    if(a<=l&&b>=r)
        return data[k];
    return query(a,b,2*k+1,l,(l+r)/2)+query(a,b,2*k+2,(l+r)/2,r);
}

int main()
{
    int t,n,a,b,v,cnt=0;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d:\n",++cnt);
        memset(data,0,sizeof(data));
        scanf("%d",&n);
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&v);
            update(v,i,0,0,n);
        }

        while(scanf("%s",s)&&s[0]!='E')
        {
            scanf("%d%d",&a,&b);
            if(s[0]=='Q')
                printf("%d\n",query(a-1,b,0,0,n));
            else
            {
                if(s[0]=='S')
                    b=-b;
                update(b,a-1,0,0,n);
            }
        }
    }
}