使用树状数组 求和

树状数组的详细讲解参照 http://fqq11679.blog.hexun.com/21722866_d.html

/*
 * 顺序给定n个数, 多次对这n个数进行两中操作
 * 1. 对第k个数进行加操作;
 * 2. 求前k项的和
 *
 * 使用树状数组
 * */

#include <stdio.h>

#define lowbit(x) ((x) & ((x) ^ (x-1)))
void add(int *C, int n, int pos, int v);





/* 初始化 */
int *init_C(int *A, int n)
{
    int *C;
    int i;

    if ((C=(int*)malloc(sizeof(int)*(n+1))) == NULL) exit(1);
    memset(C,0,sizeof(int)*(n+1));
    
    for (i=1; i<=n; i++) {
        add(C, n, i, A[i]);
    }
    return C;
}


/* 对某个元素进行加操作 */
void add(int *C, int n, int p, int v)
{
    while (p <= n) {
        C[p] += v;
        p += lowbit(p);
    }
}


/* 求前p项的和 */
int sum(int *C, int n, int p)
{
    int ret;

    ret = 0;
    while (p > 0) {
        ret += C[p];
        p -= lowbit(p);
    }
    return ret;
}

测试
int main()
{
    int A[] = {0,1,2,3,4,5,6,7,8,9};
    int n,i;
    int *C;

    n = 9;
    C = init_C(A, n);
    for (i=1;i<=n;i++)
        printf("%d\n", C[i]);
    printf("C%d: %d\n", n, sum(C,n,5));
    printf("C%d: %d\n", n, sum(C,n,9));
}