2014-01-18

神奇的树状数组（BIT）模板——HDU 1166

树状数组（Binary Indexed Trees， BIT， 二分索引树），是一种方便的处理前缀和的特殊的数据结构。

使用树状数组的好处就是它可以在O(log n)的时间内计算前缀和，并且可以在O(log n)的时间内更新数组中的某个值。

树状数组的实现依赖二进制的特殊性质，把一个前缀和分成若干个子序列的和，平均了查找和更新所需要的操作次数来达到这个目的。

/*************************************** 
* * 
* 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; 
    } 
} 

main