算法_数据结构_树状数组基础简介

🌸树状数组简介

「树状数组」也叫 Binary Indexed Tree，二进制索引树，很好地表示了「树状数组」处理数据的思路：「树状数组」里某个元素管理了原始输入数组多少数据是由下标决定的。

前缀和数组🌸

知道前缀和就可以求区间和，这是因为不同规模的区间和有重复的部分，相减以后就得到了区间和

🍁如图所示：红色部分的和 = 绿色部分的和 - 黄色部分的和。

可以定义：前缀和preSum[i] 表示 nums[0, i] 的和，则区间和 sumRange[from, to] = preSum[to] - preSum[from - 1]；
注意到 preSum[from - 1] 有下标越界的风险，通常的做法是：让前缀和数组多设置一位，为此修改定义：preSum[i]表示 nums[0, i) 的和，初始化的时候 preSum[0] = 0，则： sumRange[from, to] = preSum[to + 1] - preSum[from]。
预先计算出「前缀和」使得计算「区间和」的时间复杂度成为 O(1)。

「前缀和」数组的思路是：将原始数组进行预处理，将来需要查询数据的时候，只需要查询预处理数组的某些值即可。

要优化「修改操作」造成的线性时间复杂度，预处理数据组织成线性结构肯定是不行的，因此一种方案是把预处理的数据组织成「树形结构」，有两种数据结构：

线段树：高效处理「区间和」查询（不仅仅可以处理和、还可以处理区间最值等），单点修改；
树状数组：高效处理「前缀和」查询，单点修改。

说明：

事实上，「区间修改」也是支持的，但涉及的知识比较复杂，感兴趣的朋友可以自行查阅相关资料进行学习；
「线段树」能做的事情的范围大于「树状数组」能做的事情，「树状数组」做的事情更少、更专一，代码层面相对较简单。

线段树」和「树状数组」一样，都是对原始输入数组进行了预处理，使得在真正需要查询数据的时候，我们只需要看「预处理数组」的部分信息即可，由于组织成树形结构，「修改」和「查询」的时间复杂度都是 O(\log N)O(logN)。

思想：空间换时间。
注意：「线段树」和「树状数组」不能处理输入数组的长度有增加或者减少的情况。

线段树是一棵二叉树

红色部分表示预处理数组，蓝色部分是原始输入数组，箭头表示当前值是哪些结点的值的和。

树状数组是多叉树

红色部分表示预处理数组，蓝色部分是原始输入数组，箭头表示当前值是哪些结点的值的和。

🌸「树状数组」如何组织原始输入数据的结构

注意：和「堆」一样，树状数组的 00 号下标不放置元素，从 11 号下标开始使用。从上图可以观察到，与数组 C 的某个结点有关的数组 A 的某些结点，它们的下标之间有如下关系。

数组 `C` 的值由数组 `A` 的哪些元素而来	数组 `A` 的元素个数
`C[1] = A[1]`	1
`C[2] = A[1] + A[2]`	2
`C[3] = A[3]`	1
`C[4] = A[1] + A[2] + A[3] + A[4]`	4
`C[5] = A[5]`	1
`C[6] = A[5] + A[6]`	2
`C[7] = A[7]`	1
`C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]`	8

这件事情是由下标数值的二进制决定的，把下标写成二进制的形式，最低位的 11 以及后面的 00 表示了预处理数组 C 管理了多少输入数组 A 的元素。我们看一下下面的图：

例如：66 的二进制表示为 01100110，这里只保留最低 4 位。将 66 进行二级制分解得到：

6=1×2^2^+1×2^1^

最后的这部分 1 x 2^1^ 决定了 C[6] 管理了多少个输入数组 A 的数据，这里是 2 个，即从下标 6 开始（包括 6）向前数 2 个数，因此 C[6] = A[5] +A[6]，其它同理。

这就是开头所说的：「树状数组」里某个元素管理了原始输入数组多少数据是由下标决定的。

我们看到：

「树状数组」组织成的树是有层级的，下标的二进制表示的最低位 1 后面的 0 的个数决定了，当前结点在第几层；
这样组织数据，从叶子结点到父结点是可以通过一个叫做 lowbit 的函数计算出来，并且可以知道小于等于当前下标的同一层结点的所有结点，为了说清楚这一点，需要有一定的篇幅。

🌸lowbit 函数

这样命名的含义是截取一个正整数的二进制表示里的最低位的 11 和它后面的所有的 00。lowbit 的定义如下：

lowbit(x) = x & (-x);

说明：

这里 x 一定是正整数，即 x >= 1；
这里 & 表示按位与运算；
-x 也可以写成 (~~x + 1) ，这里 ~ 表示「按位取反」。这是负数的定义，负数用补码表示，它的值等于这个负数的绝对值按位取反以后再加 11，因此 lowbit(x) = x & (~~x + 1);

下面是一些关于负数和补码的知识，如果您比较熟悉的话，可以忽略

🌸复习负数和补码的相关知识

计算机底层存储整数使用 32 位；
最高位表示符号位：1 表示负数， 0 表示正数；
负数使用补码表示。

补码按照如下规则定义：

正数的补码是它自己；
负数的补码是它对应正整数按位取反以后再加 1。

例如：计算 -5−5 的二进制表示：

步骤	二进制表示
第 1 步：写出 5 的二进制表示；	`00000000 00000000 00000000 00000101`
第 2 步：将 5 的二进制表示按位取反；	`11111111 11111111 11111111 11111010`
第 3 步：在第 2 步的基础上再加 1。	1`1111111 11111111 11111111 11111011`

这样设计的好处是：符号位参与计算，并且保证了结果正确，我们再看一个例子。

例 2：计算 16 - 8

步骤	二进制表示
第 1 步：写出16 的二进制表示；	`00000000 00000000 00000000 00010000`
第 2 步：写出 -8 的二进制表示；	`11111111 11111111 11111111 11111000`
第 3 步：计算 16 - 8。	`00000000 00000000 00000000 00001000`

计算 16 - 816−8，直接加，高位溢出，但不影响结果。

🌸lowbit 运算解释：

先按位取反正好让最低位的 1变成 0，最低位的 1 后面的 0 变成 1，最低位的 1 前面的 1 变成 0，0 变成 1；
再加 1 使得低位的 1 全变成 0，原来变成 0 的 1 由于进位又变回了 1；
再按位取余，正好就留下了一个 1。

🌸「单点更新」与「前缀和查询」

🍁单点更新

「单点更新」从孩子结点到父亲结点，沿途所有的结点都需要更新；
从孩子结点到父亲结点，就是不断加上当前下标的 lowbit 值，产生进位。

/**
 * 单点更新
 *
 * @param i     原始数组索引 i
 * @param delta 变化值 = 更新以后的值 - 原始值
 */
public void update(int i, int delta) {
    // 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
    while (i <= len) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

public static int lowbit(int x) {
    return x & (-x);
}

🍁前缀和查询

我们使用记号 preSum[7] 表示查询 A[1] + A[2] + … + A[7]。依然是考虑 7 的二进制 (0111)2分解：

7=1×2^2^+1×2^1^+1×2^0^

这三部分可以看成 (0100)2、(0010) 2 、(0001)2
这 3 部分之和，分别表示 4 个元素 + 2 个元素 + 1 个元素，正好是 lowbit 值一直减，减到 0 为止，每减去一个 lowbit 值，消去一个 1。

/**
 * 查询前缀和
 *
 * @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
 */
public int query(int i) {
    // 从右到左查询
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

🍁树状数组的初始化

这里要说明的是，初始化前缀和数组应该交给调用者来决定。下面是一种初始化的方式。树状数组的初始化可以通过「单点更新」来实现，因为最开始的时候，数组的每个元素的值都为 0，每个都对应地加上原始数组的值，就完成了预处理数组 C 的创建。

这里要特别注意，update 操作的第 2个参数是一个变化值，而不是变化以后的值。因为我们的操作是逐层向上汇报，汇报变更值会让我们的操作更加简单。

public FenwickTree(int[] nums) {
    this.len = nums.length + 1;
    tree = new int[this.len + 1];
    for (int i = 1; i <= len; i++) {
        update(i, nums[i]);
    }
}

🍁「树状数组」的完整代码：

java

public class FenwickTree {

    /**
     * 预处理数组
     */
    private int[] tree;
    private int len;

    public FenwickTree(int n) {
        this.len = n;
        tree = new int[n + 1];
    }

    /**
     * 单点更新
     *
     * @param i     原始数组索引 i
     * @param delta 变化值 = 更新以后的值 - 原始值
     */
    public void update(int i, int delta) {
        // 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
        while (i <= len) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    /**
     * 查询前缀和
     *
     * @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
     */
    public int query(int i) {
        // 从右到左查询
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    public static int lowbit(int x) {
        return x & (-x);
    }
}

python

class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 1)]

    def __lowbit(self, index):
        return index & (-index)

    # 单点更新：从下到上，最多到 size，可以取等
    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += self.__lowbit(index)

    # 区间查询：从上到下，最少到 1，可以取等
    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.__lowbit(index)
        return res