树状数组

一、树状数组

树状数组是一个优美小巧的数据结构，在很多时候可以代替线段树。一句话概括就是，凡是树状数组可以解决的问题，线段树都可以解决，反过来线段树可以解决的问题，树状数组不一定能解决。

树状数组英文名称为Binary Index Tree，直译过来就是二进制索引树，我觉得二进制索引树更能说明其本质。树状数组的本质就是一种通过二进制位来维护一个序列前i和的数据结构。

1、更新元素

比如修改了a[3]，则：

P1 = x = 3, L1 = 0;

P2 = p1+ 2(L1) = 3 + 1 = 4, L2 = 2;

P3 = p2 + 2(L2) = 4 + 4 = 8, L3 = 3;

....

2、子序列求和

比如求sum(6)

p1 = x = 6, L1 = 1; sum += c[6];

p2 = p1 - 2(L1) = 6 - 2 = 4; L2 = 2; sum += c[4];

p3 = p2 - 2(L2) = 4 - 4 = 0, return;

二、树状数组的维护

对于维护的序列A，定义C[i]=A[j+1]+...+A[i]，其中j为i的二进制表示中把最右边的1换成0的值。j的值可以通过lowbit求出，即i-lowbit(i)。

lowbit(a)为2^(a的二进制表示末尾0的个数)。可以用下面式子求出：

lowbit(a)=a&(a ^ (a-1))
//或
lowbit(a)=a&(~a+1)
//或根据补码性质
lowbit(a)=a&(-a)

 修改方式如下

    void modify(int p,int delta)
    {
        while (p<=N)
        {
            C[p]+=delta;
            p+=lowbit(p);
        }
    }

求前缀和如下

    int sum(int p)
    {
        int rs=0;
        while (p)
        {
            rs+=C[p];
            p-=lowbit(p);
        }
        return rs;
    }

三、示例代码

package ads;

/**
 * 
 * @author loull
 * 下标index从1开始数
 */
public class BinaryIndexTree {

    int[] c;
    int n;
    public BinaryIndexTree(int n) {
        this.n = n;
        c = new int[n+1];
    }
    
    int lowbit(int x) {
        return x & (x ^ (x-1));
    }
    /**
     * 更新一个元素，初始数组c都是0，所以可以用这个方法初始化c，这时候增加与更新是等价的
     * @param p    更新第p个元素，索引从1开始
     * @param d    增加的值，不是更新后的值
     */
    void update(int p, int d) {
        while (p <= n) {
            c[p] += d;
            p += lowbit(p);
        }
    }
    
    /**
     * 计算从第一个元素到第p个元素的和
     * @param p
     * @return
     */
    int sum(int p) {
        int ret = 0;
        while (p > 0) {
            ret += c[p];
            p -= lowbit(p);
        }
        return ret;
    }
    
    public static void main(String[] args) {
        int[] numbers = {1,2,3,4,5,6,7,8,9};
        BinaryIndexTree bit = new BinaryIndexTree(numbers.length);
        for (int i=0; i<numbers.length; i++) {
            bit.update(i+1, numbers[i]);
        }
        
        System.out.println(bit.sum(9));
    }
}

四、C++模板

/***************************************
*                                      *
*    Template of Binary Indexed Tree   *
*                                      *
*           @author: Zyzsdy            *
*                                      *
****************************************
*   Thanks: shu_mj                     *
*           ACM Template of Tokyo U    *
***************************************/
template <class Type>
struct binaryIndexTree {
    Type *data;
    int size_n;
    binaryIndexTree (int _size) : size_n (_size + 1) {
        data = new Type[size_n]();
    }
    ~binaryIndexTree() {
        delete [] data;
    }
    void add (int _lower, Type _delta) {
        int pos = _lower + 1;
        while (pos < size_n) {
            data[pos] += _delta;
            pos += pos & -pos;
        }
    }
    Type sum (int _lower, int _upper) {
        if (_lower > 0) {
            return sum (0, _upper) - sum (0, _lower);
        } else {
            Type result = 0;
            int pos = _upper;
            while (pos > 0) {
                result += data[pos];
                pos -= pos & -pos;
            }
            return result;
        }
    }
};
typedef binaryIndexTree<int> BIT;

这份树状数组模板支持自动根据数据类型和数据量申请内存，单点更新和区间查询。就算不用模板，这份代码也很容易记忆。。

下面是HDU 1166，典型的树状数组题目，直接套上面的模板就可以解了。。因此不再放出完整代码，只贴上主函数，复制这两份代码再添上头文件即可运行。

int main(int agrc, char *agrv[]) {
    int T;
    scanf("%d",&T);for(int i=1;i<=T;i++){
        printf("Case %d:n",i);
        int n;
        scanf("%d",&n);
        BIT *ps=new BIT(n);
        for(int j=0;j<n;j++){
            int p;
            scanf("%d",&p);
            ps->updateDelta(j,p);
        }
        char buff[80];
        while(true){
            scanf("%s",buff);
            if(buff[0]=='E') break;
            int posi,shuj;
            switch(buff[0]){
            case 'Q':
                int l,r;
                scanf("%d%d",&l,&r);
                printf("%dn",ps->sum(l-1,r));
                break;
            case 'A':
                scanf("%d%d",&posi,&shuj);
                ps->updateDelta(posi-1,shuj);
                break;
            case 'S':
                scanf("%d%d",&posi,&shuj);
                ps->updateDelta(posi-1,-shuj);
                break;
            }
        }
        delete ps;
    }
}