线段树的入门题，数组代替树；

线段树是一种完全二叉树，主要操作有建树、修改节点、区间询问（最大值或者和等），由于采用二叉树结构，对一个结点的操作复杂为 logn；

这里建树、修改和询问操作没有采用递归方式，主要是利用了线段树也是完全二叉树的特点，因此可以直接根据要查看节点的编号（1..n）求得其对应在树中的编号，就可以直接进行操作，而不需要递归来实现。

# include 
     
      # include 
      
       # define N (1 << 17)# define M ((1 << 16) )int segSum[N];void initTree(void){    segSum[0] = 0;    memset(segSum, 0, sizeof(segSum));}int query(int Left, int Right){    int ret;    ret = 0;    Left += M-1, Right += M+1;    while ((Right ^ Left) != 1)    {                if ((Left&0x1) == 0) ret += segSum[Left+1];        if ((Right&0x1) == 1) ret += segSum[Right-1];        Left >>= 1, Right >>= 1;    }    return ret;}void add(int i, int dx){    int p;    p = i + M;    while (p != 0)    {        segSum[p] += dx;        p >>= 1;    }}int main(){    char buf[10];    int T, n, i, j, x, k;    scanf("%d", &T);    for (k = 1; k <= T; ++k)    {        initTree();        scanf("%d", &n);        for (i = 1; i <= n; ++i)        {            scanf("%d", &x);            add(i, x);        }        printf("Case %d:\n", k);        while (1)        {            scanf("%s", buf);            if (buf[0] == 'E') break;            scanf("%d%d", &i, &j);            if (buf[0] == 'Q') printf("%d\n", query(i, j));            else if (buf[0] == 'A') add(i, j);            else if (buf[0] == 'S') add(i, -j);        }    }    return 0;}
      
     

//