HDU - 1166 敌兵布阵（线段树点修改）

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll num[50005];
char cmd[105];
struct node
{
    ll l, r, sum;
}a[200005];
void build(ll loc, ll l, ll r)
{
    a[loc].l = l, a[loc].r = r;
    if(l == r)a[loc].sum = num[l];
    else
    {
        ll mid = (l + r) / 2;
        build(loc * 2, l, mid);
        build(loc * 2 + 1, mid + 1, r);
        a[loc].sum = a[loc * 2].sum + a[loc * 2 + 1].sum;
    }
    return ;
}
void ad(ll loc, ll x, ll y)
{
    ll l = a[loc].l, r = a[loc].r;
    if(l == r && l == x)a[loc].sum += y;
    else
    {
        ll mid = (l + r) / 2;
        if(x <= mid)ad(loc * 2, x, y);
        else ad(loc * 2 + 1, x, y);
        a[loc].sum = a[loc * 2].sum + a[loc * 2 + 1].sum;
    }
    return ;
}
ll qu(ll loc, ll L, ll R)
{
    ll l = a[loc].l, r = a[loc].r;
    if(l == L && r == R)return a[loc].sum;
    else
    {
        int mid = (l + r) / 2;
        if(mid >= R)return qu(loc * 2, L, R);
        else if(mid < L)return qu(loc * 2 + 1, L, R);
        else
        {
            return qu(loc * 2, L, mid) + qu(loc * 2 + 1, mid + 1, R);
        }
    }
}
int main()
{
    ll t, n, m, i, j, k, ca = 1, x, y;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld", &n);
        printf("Case %lld:\n", ca++);
        for(i = 1; i <= n; i++)
        {
            scanf("%lld", &num[i]);
        }
        build(1, 1, n);
        while(1)
        {
            scanf("%s", cmd);
            if(strcmp(cmd, "End") == 0)break;
            else if(strcmp(cmd, "Query") == 0)
            {
                scanf("%lld %lld", &x, &y);
                printf("%lld\n", qu(1, x, y));
            }
            else if(strcmp(cmd, "Add") == 0)
            {
                scanf("%lld %lld", &x, &y);
                ad(1, x, y);
            }
            else
            {
                scanf("%lld %lld", &x, &y);
                ad(1, x, -y);
            }
        }
    }
    return 0;
}