2013-team4/code/bitree

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
一维树状数组
}}}
{{{
创建
BITree t;
清空
t.clear();
将第 k 个数增加 d
t.add(k, d);
查询 0 <= i <= k 的 sum(a[i])
t.sum(k);
}}}
{{{
const int MAXN = 20005, OFFSET = 3;
typedef int DATA;

struct BITree{
    DATA a[MAXN];
    void clear(){
        memset(a, 0, sizeof(a));
    }
    int lowbit(int i){
        return (i & -i);
    }
    DATA sum(int i){
        DATA ret = 0;
        for(i += OFFSET; i > 0; i -= lowbit(i))
            ret += a[i];
        return ret;
    }
    void add(int i, DATA d){
        for(i += OFFSET; i < MAXN; i += lowbit(i))
            a[i] += d;
    }
};
}}}
{{{
二维树状数组
}}}
{{{
将第 (x, y) 个数增加 d
t.add(x, y, d);
查询 (0, 0) 到 (x, y) 的 sum
t.sum(x, y);
查询 (x1, y1) 到 (x2, y2) 的 sum
t.sum(x1, y1, x2, y2);
}}}
{{{
typedef int DATA;
const int MAXX = 105, MAXY = 105, OFFSET = 3;

struct BITree{
    DATA a[MAXX][MAXY];
    void clear(){
        memset(a, 0, sizeof(a));
    }
    int lowbit(int i){
        return (i & -i);
    }
    DATA sum(int x, int y){
        DATA ret = 0;
        for(int i = x + OFFSET; i > 0; i -= lowbit(i))
            for(int j = y + OFFSET; j > 0; j -= lowbit(j))
                ret += a[i][j];
        return ret;
    }
    DATA sum(int x1, int y1, int x2, int y2){
        DATA ret = sum(x2, y2);
        ret -= sum(x1 - 1, y2) + sum(x2, y1 - 1);
        ret += sum(x1 - 1, y1 - 1);
        return ret;
    }
    void add(int x, int y, DATA d){
        for(int i = x + OFFSET; i < MAXX; i += lowbit(i))
            for(int j = y + OFFSET; j < MAXY; j += lowbit(j))
                a[i][j] += d;
    }
};
}}}

一维树状数组

创建
BITree t;
清空
t.clear();
将第 k 个数增加 d
t.add(k, d);
查询 0 <= i <= k 的 sum(a[i])
t.sum(k);

const int MAXN = 20005, OFFSET = 3;
typedef int DATA;
struct BITree{
    DATA a[MAXN];
    void clear(){
        memset(a, 0, sizeof(a));
    }
    int lowbit(int i){
        return (i & -i);
    }
    DATA sum(int i){
        DATA ret = 0;
        for(i += OFFSET; i > 0; i -= lowbit(i))
            ret += a[i];
        return ret;
    }
    void add(int i, DATA d){
        for(i += OFFSET; i < MAXN; i += lowbit(i))
            a[i] += d;
    }
};

二维树状数组

将第 (x, y) 个数增加 d
t.add(x, y, d);
查询 (0, 0) 到 (x, y) 的 sum
t.sum(x, y);
查询 (x1, y1) 到 (x2, y2) 的 sum
t.sum(x1, y1, x2, y2);

typedef int DATA;
const int MAXX = 105, MAXY = 105, OFFSET = 3;
struct BITree{
    DATA a[MAXX][MAXY];
    void clear(){
        memset(a, 0, sizeof(a));
    }
    int lowbit(int i){
        return (i & -i);
    }
    DATA sum(int x, int y){
        DATA ret = 0;
        for(int i = x + OFFSET; i > 0; i -= lowbit(i))
            for(int j = y + OFFSET; j > 0; j -= lowbit(j))
                ret += a[i][j];
        return ret;
    }
    DATA sum(int x1, int y1, int x2, int y2){
        DATA ret = sum(x2, y2);
        ret -= sum(x1 - 1, y2) + sum(x2, y1 - 1);
        ret += sum(x1 - 1, y1 - 1);
        return ret;
    }
    void add(int x, int y, DATA d){
        for(int i = x + OFFSET; i < MAXX; i += lowbit(i))
            for(int j = y + OFFSET; j < MAXY; j += lowbit(j))
                a[i][j] += d;
    }
};