線段樹 點更新 區間和 模闆

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <math.h>
#define mem(a) memset(a,0,sizeof(a))
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;

const int maxn = ;
struct Nodes
{
    int l,r;//區間
    int sum;//區間和
} node[maxn<<];//大約需要開資料總數四倍的數組
int A[maxn];

void Pushup(int u)//維護目前線段和
{
    node[u].sum = node[L(u)].sum + node[R(u)].sum;
    return ;
}
void Build (int u,int left,int right)//建立一顆線段樹
{
    node[u].l = left,node[u].r = right;//線段端點

    if (node[u].l == node[u].r)//如果更新到葉子節點，就讓該線段的區間和等于該點的值
    {
        node[u].sum = A[left];
        return ;
    }
    int mid = (node[u].l + node[u].r)>>;//每個父節點分成兩個子節點的區間。
    Build (L(u),left,mid);//遞歸兩個子節點
    Build (R(u),mid+,right);
    Pushup(u);//維護該線段的sum是該線段的區間和。
}
void Update(int u,int pos,int val)//點更新操作。（給某個點增加或者減少某個值，更改值同理可得。）
{
    if (node[u].l==node[u].r)//如果更新到葉子節點就直接更改該節點的值。
    {
        node[u].sum += val;
        return ;
    }
    int mid = (node[u].l + node[u].r)>>;
    //看需要更新的節點的位置在目前節點的左子樹還是在目前節點的右子樹，判斷，然後遞歸修改值。
    if (pos <= mid) Update(L(u),pos,val);
    else Update(R(u),pos,val);
    Pushup(u);//遞歸操作之後，維護目前節點是目前線段的區間和。
}

int Query(int u,int left,int right)//查詢操作
{
    if (left <= node[u].l&&node[u].r <= right)
        return node[u].sum;
   //如果目前所在的區間是需要查詢的區間的子區間，那麼直接傳回該區間的區間和就OK.
    int mid = (node[u].l + node[u].r)>>;
    if (right <= mid) return Query(L(u),left,right);//遞歸查詢子區間，求區間和。
    else if (left > mid) return Query(R(u),left,right);
    else return (Query(L(u),left,mid) + Query(R(u),mid+,right));
    Pushup(u);//可有可無。
}
int main ()
{
#ifndef ONLINE_JUDGE
    freopen("1","r",stdin);
#endif // ONLINE_JUDGE
    ios_base::sync_with_stdio(false);//cin cout的輸入輸出與scanf printf同步，資料量大時省時間。
    cin.tie();

    int T,n,m,t,i,x,add,a,b;
    char s[];
    scanf("%d",&T);
    for(t = ; t <= T; t++)
    {
        scanf("%d",&n);
        printf("Case %d:\n",t);
        for(i = ; i <= n; i ++)
        {
            scanf("%d",&A[i]);
        }
        Build(,,n);
        while()
        {
            scanf("%s",s);
            if(strcmp(s,"Add") == )
            {
                scanf("%d%d",&x,&add);
                Update(,x,add);
            }
            else if(strcmp(s,"Sub") == )
            {
                scanf("%d%d",&x,&add);
                Update(,x,-add);
            }
            else if(strcmp(s,"Query" ) == )
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",Query(,a,b));
            }
            else
            {
                break;
            }
        }
    }
    return ;
}