刘汝佳：《训练指南》Page（194）


#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>using namespace std;//一维树状数组基础模板int lowbit(int x){    return x&(-x);}int c[1001];int sum(int x) //计算从1到x的数组元素的和{    int s=0;    while(x>0)    {        s=s+c[x];        x=x-lowbit(x);    }    return s;}void add(int x, int d ) //将A(x)的值增加d，也可以减掉某个值{    while(x<=1000) //此处的1000只是我开的数组的封顶，这是根据题目的数据进行更改的    {        c[x]=c[x]+d;        x=x+lowbit(x);    }}int main(){    int a[1001];    int i, j;    for(i=0; i<=1000; i++ )    {        a[i]=i;    }    c[0]=0;    for(i=1; i<=1000; i++) //有a[]数组进行计算c[]数组的值    {        c[i]=0;        for(j=i-lowbit(i)+1; j<=i; j++ )        {            c[i]=c[i]+a[j];        } //    }    int x;    scanf("%d", &x);    printf("%d\n", sum(x) ); //查询1->x的a[]的和    int y;    scanf("%d", &y);    add(x, y); //a[]下标为x的元素增加d    printf("%d\n", sum(x));    return 0;}