敌兵布阵

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 36928    Accepted Submission(s): 15589

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

Case 1:
6
33
59

心得：

lowbit()这个函数真的很奇妙，也很强大。树状数组处理区间统计问题写起代码来很简洁，搞笑，比线段树空间复杂度低，但是适用范围没有线段树广。更新和查询的操作主要是我觉得就是“爬树”和“下树”的过程，过程中进行信息的统计。这个过程并不一定是依照节点之间边的关系来进行的，也可能从一个节点跳到另一个与它没有关系的节点，在这里lowbit()这个函数起着重要的作用。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=50002;
int c[maxn];
int n;char cm[10];

int lowbit(int x)
{
    return x&(-x);
}
void update(int i,int x)//从小向大更新，不一定沿着边
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
int sum(int i)//从大向小查询，沿路相加，求出前i个数的和
{
    int s=0;
    while(i>0)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

int main()
{
    int t;scanf("%d",&t);
    for(int ti=1;ti<=t;ti++)
    {
        memset(c,0,sizeof(c));
        printf("Case %d:\n",ti);
        scanf("%d",&n);
        int x;
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&x);
            update(j,x);
        }
        int a,b;
        while(scanf("%s",cm))
        {
            if(cm[0]==‘E‘)
                break;
            else if(cm[0]==‘A‘)
            {
                scanf("%d%d",&a,&b);
                update(a,b);
            }
            else if(cm[0]==‘S‘)
            {
                scanf("%d%d",&a,&b);
                update(a,-b);
            }
            else
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",sum(b)-sum(a-1));
            }
        }
    }
    return 0;
}

[ACM] hdu 1166 敌兵布阵（树状数组）,布布扣,bubuko.com

[ACM] hdu 1166 敌兵布阵（树状数组）

原文：http://blog.csdn.net/sr_19930829/article/details/24128249