树状数组

Aug 28 2020 更新日期:Aug 28 2020

先思考这样的问题，有一频繁变更的数组，同时需频繁求解下标范围[a,b]的和。有什么好方法可以优化变更与求和的效率？

传统方法无法两者操作均做到兼顾，要么变更复杂度O(1)，求和O(N)；或者求和O(1)，更新O(N)。

求和O(N)，更新O(1)。arr[i]表示原始元素，则更新的时候直接赋值即可，而求范围和就需要从arr[a]+…+arr[b]。

求和O(1)，更新O(N)。提前求和，arr[i]表示arr[0]+…+arr[i]，那么求范围和时只需arr[b]-arr[a]即可，但这样做更新时就需要把所有覆盖该元素的和重新计算一遍。

今天介绍优秀的树状数组(BIT, Binary Indexed Trees)，可同时将变更、求和的操作均优化到log(N)。树状数组仍然是个数组，树只是逻辑上的抽象，当然树也可以以数组表示。

这里需要先讲解几个位运算的知识。

我们知道负数用二进制表示的时候是使用取反加1进行表示的。比如10，二进制位00001010，那么-10就是11110110。(这里因篇幅原因仅以长度为8位进行举例)

那么i&-i得到的结果是什么呢？

00001010

11110110

00000010

可以看到该操作的目的是为了得到最右边的1。顺便提一下，i&-i主要是用来判断是否为二次幂，若该操作得到的结果仍是自己，那么就是二次幂。

那么这个位运算在BIT中有何作用呢？

我们将第i&-i位称为lowbit位。在BIT中，lowbit位管辖了[i-(i&-i), i]的数据和。

我们以例子来说明。i表示下标，arr表示数据数组，i&-i为lowbit，bit就是树状数组。为了方便讲解，我们把下标从1开始，0这列可以不用看。接下来将讲解如何构造bit。

初始数组arr为{2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}。bit[2]就是arr[2]+arr[1]，bit[4]就是arr[1:4]之和。依此类推边可构造出该BIT。

i      0 1 2 3 4 5 6 7 8  9 10 11 12
arr    0 2 1 1 3 2 3 4 5  6 7  8  9
i&-i   0 1 2 1 4 1 2 1 8  1 2  1  4
bit    0 2 3 1 7 2 5 4 21 6 13 8  30

下面这张图更能直观地展示BIT的数据结构，及lowbit的作用。

我们已经知道在BIT中，第i位其实是管理以自身位开始的前i&-i个数的和。那么如果求前11个元素的和该如何求解呢？根据11的二进制表达式，为1011，即1+2+8。

先看11的lowbit，发现是1，也就是说在BIT中，11只管着自己这个数，即bit[11]就是arr[11]。

减去上一个lowbit(1)后，即i-(i&-i)。发现是2，也就是说在BIT中，10管着的数是10和9，即bit[10] = arr[10]+arr[9]。

继续上一个lowbit(2)后。发现是8，也就是说在BIT中，8管着的数是前8个数的和，即bit[8] = arr[1]+…arr[8]。

综上，前11个数的和需要bit[11]+bit[11-1]+bit[11-1-2]=8+13+21=42。

可以把整个BIT看成一棵树，求范围和的复杂度为log(N)。

如果这时候需要更新arr[3]呢？在BIT中，根据lowbit计算后发现3,4,8管着arr[3]。所以只需要依此更新i+(i&-i)即可。

Jonathenzc's Blog