hdoj 1166 敌兵布阵

    暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出

    数组数组最适宜的用途就是区间求和和点的更新，但树状数组并不适用于区间的更新问题，也不是做不到，比较麻烦且难理解，有兴趣的可以看看这个http://blog.csdn.net/xindoo/article/details/8748410

//树状数组
#include<stdio.h>

int n,ans[50005],f[50005];

int lowbit(int n)
{
    return n&(-n);
}

void add(int i,int v)
{
    while(i <= n)
    {
        ans[i] += v;
        i += lowbit(i);
    }
}

int query(int n)
{
    int s = 0;
    while(n)
    {
        s += ans[n];
        n -= lowbit(n);
    }
    return s;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int j = 1;j <= t; j++)
    {
        scanf("%d",&n);
        for(int l = 1; l <= n;l++)
        {
            scanf("%d",&f[l]);
            f[l] += f[l-1];
        }
        for(int l = 1; l <= n; l++)
            ans[l] = f[l]-f[l-lowbit(l)];
        printf("Case %d:\n",j);
        while(1)
        {
            char s[20];
            int a,b;
            scanf("%s",s);
            if (s[0] == 'E') break;
            scanf("%d%d",&a,&b);
            if (s[0] == 'A') add(a,b);
            if (s[0] == 'S') add(a,-b);
            if (s[0] == 'Q') printf("%d\n",query(b)-query(a-1));
        }
    }
    return 0;
}

//线段树解法
#include <stdio.h>
#include <string.h>
#define maxn 50005

struct node
{
    int l, r, m;
    int sum;
}tree[maxn<<2];

int a[maxn];

void build(int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    int m = (l+r)>>1;
    tree[o].m = m;
    if (l == r)
    {
        tree[o].sum = a[l];
        return;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;
 }

void update(int l, int v, int o)
{
    tree[o].sum += v;
    if (tree[o].l == l && tree[o].r == l)
        return;
    if (l <= tree[o].m)
        update(l, v, o<<1);
    else
        update(l, v, (o<<1)+1);
}

int query(int l, int r, int o)
{
    if (tree[o].l == r && tree[o].r == r)
        return tree[o].sum;
    if (tree[o].m >= r)
        return query(l, r, o<<1);
    else if (tree[o].m <l)
        return query(l, r, (o<<1)+1);
    else
        return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
}

int main()
{
    int t, n;
    scanf("%d",&t);
    for (int j = 1; j <= t; j++)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        build(1, n, 1);
        printf("Case %d:\n",j);
        while(1)
        {
            char s[20];
            int l, r;
            scanf("%s",s);
            if (s[0] == 'E')
                break;
            scanf("%d%d",&l,&r);
            if (s[0] == 'A')
                update(l, r, 1);
            else if (s[0] == 'S')
                update(l, -r, 1);
            if (s[0] == 'Q')
                printf("%d\n",query(l, r, 1));
        }
    }
    return 0;
}