树状数组的奇妙运用

树状数组是一种能够在线维护前缀和的数据结构, 其写法简单常数小... 不具体介绍了, 看看一些奇妙的操作吧.

人人都会的

单点修改, 区间查询: 基本维护前缀和
区间修改, 单点查询: 维护差分

区间修改, 区间查询

引入数组, 表示区间中需要加值的差分, 进行区间加法时, 就直接对操作, 对加上, 对减去. 查询前缀和时, 设为区间的元素和, 易得

发现我们需要维护, , 的前缀和. 代码可以这样写:

int suma[MAXN], sumd[MAXN], sumdi[MAXN];

void update(int* c, int pos, int x) {
    while (pos <= n) {
        c[pos] += x;
        pos += lowbit(pos);
    }
}

void sum(int* c, int pos) {
    int res = 0;
    while (pos >= 1) {
        res += c[pos];
        pos -= lowbit(pos);
    }
}

void add(int l, int r, int x) {
    update(sumd, l, x);
    update(sumd, r + 1, -x);
    update(sumdi, l, l * x);
    update(sumdi, r + 1, -(r + 1) * x);
}

int query(int l, int r) {
    return suma[r] + r * sum(sumd, r) + sum(sumdi, r)
           - (suma[l - 1] + (l - 1) * sum(sumd, l - 1) + sum(sumdi, l));
}

二维前缀和

首先, 由二维前缀和求矩阵的操作方法:

用树状数组维护二维前缀和的方法:

void update(int x, int y, int val) {
    while (x <= n) {
        int t = y;
        while (t <= m) {
            c[x][t] += val;
            t += lowbit(t);
        }
        x += lowbit(x);
    }
}

int query(int x, int y) {
    int res = 0;
    while (x >= 1) {
        int t = y;
        while (t >= 1) {
            res += c[x][t]
            t -= lowbit(t);
        }
        x -= lowbit(x);
    }
    return res;
}

因此不难做到二维单点修改, 矩阵查询.

二维矩阵修改, 矩阵查询

首先说明一下二维差分怎么写. 由二维前缀和的形式, 定义

因此

即可用二维树状数组维护差分.

比如给一个的矩阵中间的部分加上, 可以这么修改差分数组:

0  0  0  0  0
0 +x  0  0 -x
0  0  0  0  0
0  0  0  0  0
0 -x  0  0 +x

所以矩阵修改操作的写法:

void add(int x1, int y1, int x2, int y2, int x) {
    update(x1, y1, x);
    update(x1, y2 + 1, -x);
    update(x2 + 1, y1, -x);
    update(x2 + 1, y2 + 1, x);
}