线段树之单点更新求和hdoj1166

逃离我推掉我的手 2022-09-20 15:21 184阅读 0赞

题目：hdoj1166

分析：题意很清晰，就是让你给某个点又增加或者减少x个，然后求某一段有多少个，我是用一个father数组保存叶子节点的编号，然后直接从当前节点开始，更轻到root就ok。

查询的话，从根节点开始，看在左子区间还是右子区间，直接查询到某一段全部在要查询的区间内，求和就ok，很简单。

代码：

#include <cstdio>
    #include <string>
    #include <iostream>
    using namespace std;
    const int N = 55000;
    struct Node
    {
        
        int l,r;
        int sum;
    };
    Node tree[4*N];
    int a[N];
    int fa[N];
    void build(int l,int r,int v)
    {
        
        tree[v].l=l;
        tree[v].r=r;
        if(l==r)
        {
        
            fa[l]=v;
            tree[v].sum=a[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,v*2);
        build(mid+1,r,v*2+1);
        tree[v].sum=tree[v+v].sum+tree[v+v+1].sum;
    }
    
    void update(int t,int p)
    {
        
        tree[t].sum+=p;
        if(t==1)
            return ;
        update(t/2,p);
    }
    int queue(int a,int b,int v)
    {
        
        if(tree[v].l==a&&tree[v].r==b)
        {
        
            return tree[v].sum;
        }
        int mid=(tree[v].l+tree[v].r)>>1;
        if(b<=mid) return queue(a,b,v+v);
        else if(a>mid) return queue(a,b,v+v+1);
        else return queue(a,mid,v*2)+queue(mid+1,b,v*2+1);
    }
    int main()
    {
        
        int T,n;
        char str[10];
        int x,y;
        scanf("%d",&T);
        for(int cas=1; cas<=T; cas++)
        {
        
            scanf("%d",&n);
            for(int i=1; i<=n; i++)
                scanf("%d",&a[i]);
            build(1,N,1);
            printf("Case %d:\n",cas);
            while(scanf("%s",str)>0)
            {
        
                if(str[0]=='A')
                {
        
                    scanf("%d %d",&x,&y);
                    update(fa[x],y);
                }
                else if(str[0]=='S')
                {
        
                    scanf("%d %d",&x,&y);
                    update(fa[x],-y);
                }
                else if(str[0]=='Q')
                {
        
                    scanf("%d %d",&x,&y);
                    int ans=queue(x,y,1);
                    printf("%d\n",ans);
                }
                else
                {
        
                    break;
                }
            }
        }
    }