树状数组的模板

int BIT[1000], a[1000], n;
void update(int x, int val)
{
      for(; x <= n; x += x&-x)
        BIT[x] += val;
}
int query(int x)
{
     int sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}

int main()
{
     scanf(“%d”, &n);
     int i;
     for(i = 1; i <= n; i++)
     {
           scanf(“%d”, &a[i]);
           update(i, a[i]);
     }
     printf(“sum of first 10 elements is %d
”, query(10));
     printf(“sum of all elements in range [2, 7] is %d
”, query(7) – query(2-1));
     return 0;
}

　　待解决类似问题：  历届试题 小朋友排队  http://lx.lanqiao.cn/problem.page?gpid=T123