一维树状数组（HD1166）

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<string.h>

using namespace std;

#define BITMAX 50001        //数组大小

typedef int valueType;    //元素类型定义

valueType BITree[BITMAX];    //一维树状数组，初始化

/* 2^k k表示节点编号 x 二进制末尾 0 的个数 */

inline int lowbit(int x)

{

    return x & (-x);

}

/* 一维，C[x]=A[ x-lowbit(x)+1 ....... x ] */

/* 节点 x 的值增加 add */

/* x 不能为 0 ，，应该从 1 起步，否则无限循环下去 */

inline void addPoint(int x, int add, int n)

{

    for (int i = x; i <= n; i += lowbit(i)){

        BITree[i] += add;

    }

}

/* 获取前 x 项和*/

inline valueType readSum(int x)

{

    valueType sum = ;

    for (int i = x; i > ; i -= lowbit(i))

        sum += BITree[i];

    return sum;

}

int main()

{

    int t, n;

    char s[];

    int a, b;

    scanf("%d", &t);

    for (int w = ; w <= t; ++w){

        printf("Case %d:\n", w);

        scanf("%d", &n);

        memset(BITree, , sizeof(BITree));

        for (int i = ; i <= n; ++i){

            scanf("%d", &a);

            addPoint(i, a, n);

        }

        while (scanf("%s",s) && s[] != 'E'){

            switch (s[])

            {

            case 'A':

                scanf("%d %d", &a, &b);

                addPoint(a, b, n);

                break;

            case 'S':

                scanf("%d %d", &a, &b);

                addPoint(a, -b, n);

                break;

            case 'Q':

                scanf("%d %d", &a, &b);

                printf("%d\n", (readSum(b) - readSum(a - )));

                break;

            default:

                break;

            }

        }

    }

}