学步园

题意要求支持三个操作。

Add(i,j);           //点i处增加j

Sub(i,j);           //点i处减少j

Query(i,j);        //查询区间[i,j]的和

1、树状数组

#include <stdio.h>
#include <string.h>
typedef int LL;
const int MAXN = 50000 + 10;
int C[MAXN], n;

int lowbit(int x) {return (x&-x);}
void add(int i, int d) {for(; i <= n; i += lowbit(i)) C[i] += d;}
LL query(int i) {LL ret = 0; for(; i > 0; i -= lowbit(i)) ret += C[i]; return ret;}
int main()
{
    int T, cas, x, i, j;
    char cmd[10];
    scanf("%d",&T);
    for(cas=1; cas<=T; ++cas) {
        scanf("%d",&n);
        memset(C, 0, sizeof(int)*(n+1));
        for(i=1; i<=n; ++i) {
            scanf("%d",&x);
            add(i, x);
        }
        printf("Case %d:\n",cas);
        while(1) {
            scanf("%s",cmd);
            if(cmd[0] == 'E') break;
            scanf("%d%d",&i,&j);
            if(cmd[0] == 'A') {
                add(i, j);
            }else if(cmd[0] == 'S') {
                add(i, -j);
            }else if(cmd[0] == 'Q') {
                printf("%d\n",query(j) - query(i-1));
            }
        }
    }
    return 0;
}

2、线段树

( update:单点增减 query:区间求和 )

#include <cstdio>
#include <cstring>
using namespace std;


#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
const int maxn = 55555;
struct point
{
    int l, r;
    int sum;
    int mid(){
        return (l+r)>>1;
    }
}tree[maxn*4];
int num[maxn];


void build(int rt, int l, int r) 
{
    tree[rt].l = l;
    tree[rt].r = r;
    if(tree[rt].l == tree[rt].r) {
        tree[rt].sum = num[l];
        return;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    build(LL(rt), l, mid);
    build(RR(rt), mid+1, r);
    tree[rt].sum = tree[LL(rt)].sum + tree[RR(rt)].sum;
}
void update(int rt, int pos, int val) 
{
    if(tree[rt].l == tree[rt].r) {
        tree[rt].sum +=val;
        return;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(pos<=mid) update(LL(rt), pos, val);
    else   update(RR(rt), pos, val);
    tree[rt].sum = tree[LL(rt)].sum + tree[RR(rt)].sum;
}


int query(int rt, int l, int r) 
{
    if(l <= tree[rt].l && r >= tree[rt].r) 
        return tree[rt].sum;
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    int ret = 0;
    if(l <= mid) ret  += query(LL(rt), l, r);
    if( r > mid) ret += query(RR(rt), l, r);
    return ret;
}<span style="font-family: 'Courier New', Courier; white-space: pre-wrap;">/*如果恰好题中要求解的区间在左儿子或者右儿子中，那么直接返回其所在的节点的值，否则把左儿子和右儿子中的区间加起来返回*/</span>

int main()
{
    int T, n, i, a, b, val;
    char str[10];
    scanf("%d",&T);
    for(int cas = 1; cas<=T; ++cas) {
        scanf("%d",&n);
        for(i=1; i<=n; ++i) scanf("%d",&num[i]);
        build(1,1,n);
        printf("Case %d:\n", cas);
        while(1)
        {
            scanf("%s",str);
            if(str[0]=='E') break;
            if(str[0]=='Q'){
                scanf("%d%d",&a,&b);
                printf("%d\n",query(1,a,b));
            } 
            else if(str[0]=='A') {
                scanf("%d%d",&a,&val);
                update(1,a,val);
            }
            else if(str[0]=='S') {
                scanf("%d%d",&a,&val);
                update(1,a,-val);
            }
        }
    }
}

线段树（update: 2014.07.15）

#include <stdio.h>
#include <string.h>

const int maxn = 50000 + 5;
int SUM[maxn<<4];
int num[maxn];

void PushUp(int rt)
{
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}
void build(int rt, int l, int r)
{
    if(l == r)
    {
        SUM[rt] = num[l];
        return ;
    }
    int m = (l+r)>>1;
    build(rt<<1, l, m);
    build(rt<<1|1, m+1, r);
    PushUp(rt);
}

void update(int rt, int l, int r, int p, int v)
{
    if(l == r)
    {
        SUM[rt] += v;
        return ;
    }
    int m = (l+r)>>1;
    if(p<=m) update(rt<<1, l, m, p, v);
    if(p>m) update(rt<<1|1, m+1, r, p, v);
    PushUp(rt);
}

int query(int rt, int l, int r, int L, int R)
{
    if(L<=l && r<=R)
    {
        return SUM[rt];
    }

    int m = (l+r)>>1;
    int ret = 0;
    if(L<=m) ret += query(rt<<1, l, m, L, R);
    if(R>m)  ret += query(rt<<1|1, m+1, r, L, R);
    return ret;
}
int main()
{
    int t, i, n, a, b;
    scanf("%d", &t);
    for(int cas=1; cas<=t; ++cas)
    {
        printf("Case %d:\n", cas);
        scanf("%d", &n);
        for(i=1; i<=n; ++i) scanf("%d", &num[i]);
        build(1, 1, n);
        char cmd[10];
        while(scanf("%s", cmd))
        {
            if(cmd[0]=='E') break;
            scanf("%d%d", &a, &b);
            if(cmd[0] == 'Q')
            {
                int ret = query(1, 1, n, a, b);
                printf("%d\n", ret);
            }
            else if(cmd[0] =='S')
            {
                update(1, 1, n, a, -b);
            }
            else if(cmd[0]=='A')
            {
                update(1, 1, n, a, b);
            }
        }
    }
    return 0;
}