单点修改区间求和线段树模板

清疚 2021-11-09 02:32 383阅读 0赞

#include <stdio.h>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    #define maxn 500010
    
    using namespace std;
    
    struct point
    {
         
        int l,r,val;
    }tr[maxn*4];
    
    int m,n;
    int a[maxn];
    
    void buildtree(int x,int l,int r)
    {
         
        tr[x].l=l;
        tr[x].r=r;
        if(l==r)
        {
         
            tr[x].val=a[l];
            return;
        }
        int lch=x*2,rch=x*2+1;
        int mid=(l+r)/2;
        buildtree(lch, l, mid);
        buildtree(rch, mid+1, r);
        tr[x].val=tr[x*2].val+tr[x*2+1].val;
    }
    
    void modify(int x,int pos,int val)
    {
         
        if(tr[x].l==tr[x].r)
        {
         
            tr[x].val+=val;
            return;
        }
        int mid=(tr[x].l+tr[x].r)/2;
        if(pos<=mid)
            modify(x*2, pos, val);
        else
            modify(x*2+1, pos, val);
        tr[x].val=tr[x*2].val+tr[x*2+1].val;
    }
    
    int query(int x,int l,int r)
    {
         
        if(l<=tr[x].l && tr[x].r<=r)
            return tr[x].val;
        int mid=(tr[x].l+tr[x].r)/2;
        int ans=0;
        if(l<=mid)
            ans+=query(x*2, l, r);
        if(r>mid)
            ans+=query(x*2+1, l, r);
        return ans;
    }
    
    int main()
    {
         
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        buildtree(1, 1, n);
        for(int i=1;i<=m;i++)
        {
         
            int op;
            scanf("%d",&op);
            if(op==1)
            {
         
                int x,k;
                scanf("%d%d",&x,&k);
                modify(1, x, k);
            }
            else
            {
         
                int x,y;
                scanf("%d%d",&x,&y);
                printf("%d\n",query(1, x, y));
            }
        }
    }

转载于:https://www.cnblogs.com/ShineEternal/p/10834219.html