[Leetcode] 树状数组

satjd

2019/11/02

Categories: Algorithm 基础知识 Tags: leetcode

树状数组的用途

多次单点更新的前提下,优化区间查询的效率

例如:在求数组区间和的场景下,如果我们使用前缀和数组来保存前缀,区间和的查询操作sum[i+1,j] = prefix[j] - prefix[i]时间复杂度是O(1),但数组更新时,前缀和数组的更新效率是O(n)。

但如果对原数组维护一个树状数组,则更新操作的时间复杂度可以降低到O(log n),查询操作提升到O(log n),在更新操作频繁时,这种数据结构能够优化更新操作的时间复杂度。

相比于线段树,树状数组的实现更简单,空间复杂度更低,但使用场景不如线段树多。

例子:

扩展1:其实,上面的区间查询+单点更新也可以推广到区间更新+单点查询,需要将原数组转化成差分数组。这样就可以将区间更新转换成点更新,单点的查询也可以转化成对一个区间的求和。例子:HDU 1556

扩展2区间更新+单点查询可以继续扩展为区间更新+区间查询,思路是维护两个树状数组,分别用来求delta[x]delta[x] * x 的前缀和,其中delta为差分数组。参考https://blog.csdn.net/qq_21841245/article/details/43956633

数据结构定义

来源:https://www.hackerearth.com/zh/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

例如:原数组为:

//for ease, we make sure our given array is 1-based indexed
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

BIT[i]是从i开始往前算lowbit(i)个数字之和。 lowbit(i)是指从i的二进制表示的最低位开始数,有k位0,则lowbit(i) = 2^k

举例:12 用二进制表示为 1100 则lowbit(12) = 2^2 = 4 则BIT[12]=a[12]+a[11]+a[10]+a[9]

可以观察到,到第i位的前缀和是BIT[i] + BIT[i-lowbit(i)] + BIT[i-lowbit(i) - lowbit(i-lowbit(i))] …

如 i=15时,1至15的前缀和为BIT[15]+BIT[15 - lowbit(15) = 14]+BIT[14-lowbit(14)=12]+BIT[12-lowbit(12)=8]+BIT[8-lowbit(8)=0]

BIT[0]约定为0,则最后BIT[15]=BIT[14]+BIT[12]+BIT[8]

在更新时,则与查询的顺序反过来,假设要更新的是a[i],则BIT中需要更新的是:BIT[i], BIT[i+lowbit(i)], BIT[i+lowbit(i) + lowbit(i+lowbit(i))]

如 a[9] += 1 更新时需要更新的BIT位置为: BIT[9] , BIT[9+lowbit(9)=10], BIT[10+lowbit(10)=12], BIT[12+lowbit(12)=16]

实现

lowbit

// 利用负数补码的性质
private int lowbit(int x) {
    return x & (-x);
}

update

// 向原数组的第X位加1,可以扩展到加任意值的情况
private void addToX(int[] bit, int x) {
    while (x < bit.length) {
        bit[x]++;
        x += lowbit(x);
    }
}

query

// 查询[1,pre]这个区间内的sum
private int query(int[] bit, int pre) {
    int ret = 0;
    while(pre > 0) {
        ret += bit[pre];
        pre -= lowbit(pre);
    }
    return ret;
}