树状数组（Binary Indexed）

首先很感谢B站up主鹤翔万里的视频, 推荐看 https://www.bilibili.com/video/av69667943?from=search&seid=10916758362943551299 本文为这个视频集合算法笔记写的总结

问题引入：给出了一个长度为n的数组，完成以下两种操作

输出区间[x, y]内每个数字的和
将第x个数加上k

最基础的算法：

维护一个sum数组，其sum[i]记录的为从0-i的和。其递推计算关系为sum[i] = sum[i-1] + nums[i]其中sum[0] = nums[0]。
计算区间和即可使用sum_xy = sum[y] - sum[x-1]。
将第x个数加上v, 因为要更新sum[x]...sum[n]所有值，因此其时间复杂度为$O(n)$
如果进行k次操作add则时间复杂度为$O(kn)$，k次求区间和的时间复杂度为$O(k)$

在更新频繁的很多场景下$O(kn)$的时间复杂度是不可接受的。

因此引入树状数组来解决此问题。

树状数组(Binary Indexed Tree)：单点修改$O(logn)$，区间查询$O(logn)$，因此在区间内多次修改查询的速度为$O(klogn)$

LowBit 运算

非负证数n在二进制表示下最低为1及其后面的0构成的数值。例如:

$$lowbit(20) = lowbit(10100) = (100) = 4$$

如何操作呢:

c++代码

int lowbit(unsigned int n) {
    /**
     *  10100  20
     *  01100  20的补码
     * &------
     *  00100->lowbit
    */
    unsigned int complement_n = ~n + 1; // 求补码，如果是int的话直接 -n即可
    return n & complement_n; 
}
// 或者

int lowbit(int n) {
    return n & (-n)
}

python代码

def lowbit(n):  # lambda n: n & (-n)
    return n & (-n)

树状数组

树状数组仍旧是用一个类似于sum的数组去维护一些和的信息(t)，但是t[i]维护的不是前i个数的和，维护的是i号位置之前（包含i）lowbit(i)的整数加和。显然t[i]覆盖长度为lowbit(i)。

注意!：树状数组的下标一定是从1开始

其中

t[1] = A[1]
t[2] = A[1] + A[2]
t[3] = A[3]
t[4] = A[1] + A[2] + A[3] + A[4]
t[5] = A[5]
t[6] = A[5] + A[6]
t[7] = A[7]
t[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] …

依次类推

再看前面提到的两个问题：

add(x, k): 给第x的数加上一个k的值。按照树状数组的定义，在A[x] += k操作后所有包含A[x]的t的节点都要更新。

观察到一个特点：

即t[x]的父节点为t[x+lowbit(x)]，A[x]的父节点是t[x]

因此如果要更新所有包含A[x]的节点，即一直更新A[x]的父节点即可，直到更新到最后一个父节点。

void add(x, k) {
    for (; x <= n; x += lowbit(x)) t[x] += k;
}

ask(x): 得到索引从1到x之间A[]的和:

由于上面提到的t[x]包含从x到x-bitlow(x)标记的数字，因此ask(x) = t[x] + ask(x - bitlow(x))，结束条件是 x == 0

int ask(x) {
    int ans = 0;
    for (; x > 0; x -= lowbit(x)) ans += t[x];
}

二维的树状数组

add函数设计

void add(int x, int y, int k) {
    for (; x <= n; x += lowbit(x)) {
        for (; y <= n; y += lowbit(y)) {
            t[x][y] += k;
        }
    }
}

ask 函数设计

int ask(int x, int y) {
    int ans = 0;
    for (; x; x -= lowbit(x))
        for (; y; y-= lowbit(y))
            ans += t[x][y]
    return ans;
}

区间更新，单点查询

问题：

设计单点查询，返回A[x]
设计区间修改，将A[1]~A[x]每个值加k

原有的树状数组的定义已经无法满足使用，因为add操作在原有的树状数组下会特别复杂。

因此引入差分数组b，然后用树状数组t维护其前缀和。

以下是oi-wiki的介绍(https://oi-wiki.org/basic/prefix-sum/)

差分，是一种和前缀和相对的策略。这种策略是，令$b_i = a_i - a_{i-1}$ ，即相邻两数的差。易得对这个序列做一遍前缀和就得到了原来的$a$序列。它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。（总之修改操作一定要在查询操作之前）具体怎么搞？譬如使$[l, r]$每个数加上一个 $b_l := b_l + k$，就是 $b_{r+1} := b_{r+1} - k$。最后做一遍前缀和就好了。

具体来说就是维护差分的话$b_l = A_l - A_{l-1} = A_l + k - (A_{l-1} + k) $ 则$b_l + k = A_l + k - A_{l+1}$。

因此:

单点查询就等于使用t维护的数组做如下操作 a[x] + ask(x)
区间修改就等于使用t维护的数组做如下操作 add(1, d); add(x+1, -d)

区间更新，区间查询

对于区间更新和区间查询，我们也可以使用差分的方式去求解，只不过使用的是前缀和的差分。

首先数组A的考虑差分$b_{i}$，则前缀和的差分

$$\sum_{i=1}^{x} a_{i} - \sum_{i=1}^{x-1} a_{i} = a_{i} - a_{i - 1} + a_{i-i} - a{i-2} .... + a_{2} - a_{1} + a{1} = b_{i} + b_{i-1} + ... + b_{1} = \sum_{i=1}^{x}b_{i}$$

前缀和差分的前缀和

$$\sum_{i=1}^{x}\sum_{j=1}^{i} b_{j}$$

使用树状数组去维护前缀和的差分的前缀和

但是类似上图，为了方便计算，引入另一个树状数组去存储$\sum_{i=1}^{x} i \times b_{i}$

代码

t1维护b[i]的前缀和，t2维护i*b[i]的前缀和

在区间[l, r] 加上d

// t1
add1(l, d)
add1(r+1, -d)
// t2
add2(l, l*d)
add2(r+1, -(r+1)*d)

查询区间[l, r]的和

ans = (sum[r] + (r+1) * ask1(r) - ask2(r)) - (sum[l-1] +  l*ask(l-1) - ask2(l-1))

进一步拓展

树状数组维护的值不仅仅是求和，也可以是最大值最小值等信息。可以这样拓展此数组

它的核心就是,前缀区间和的维护.

树状数组的应用

求逆序数的个数或者顺序数的个数（剑指offer No.51 ）.
求一个序列第k大的数（Leetcode No.215 Kth Largest Element in an Array）典型的需要hash前缀或者后缀和的题目.
Leetcode 218. The Skyline Problem 等等。。。

参考

强烈推荐!!!!!!!! https://www.bilibili.com/video/av69667943?from=search&seid=10916758362943551299
《算法笔记》
https://oi-wiki.org/basic/prefix-sum/

查看原始Issue