chat

详细介绍一下 BIT 树状数组

什么是树状数组 (BIT)？

树状数组（Binary Indexed Tree，简称 BIT）是一种高效的数据结构，主要用于处理前缀和相关的问题。

它支持以下操作：

  1. 前缀查询：查询数组从索引 1 到索引 i 的前缀和。
  2. 单点更新：将数组的某个元素增加或减少一个值。

树状数组的时间复杂度为 (O(\log n))，适合动态维护数组的前缀和。

树状数组的核心思想

树状数组通过构造一个辅助数组 BIT 来存储部分前缀和信息，从而在 (O(\log n)) 时间内完成前缀查询和更新。

  1. BIT[i] 的含义：BIT[i] 存储从索引 i - 2^r + 1 到索引 i 的区间和，其中 (r) 是 (i) 的二进制表示中最低位 1 的位置。例如：
    • (BIT[1] = arr[1])
    • (BIT[2] = arr[1] + arr[2])
    • (BIT[4] = arr[1] + arr[2] + arr[3] + arr[4])
  2. 通过维护这种区间和关系，可以递归分解任意前缀和或更新操作。

核心公式

  1. 最低有效位（Lowest Significant Bit，LSB）计算： 
    LSB(i) = i & -i
    • (LSB(4) = 4 & -4 = 4)
    • (LSB(6) = 6 & -6 = 2)
  2. 更新操作：将索引 i 的值增加 delta，影响所有包含 i 的区间。 
    i += LSB(i)
  3. 前缀和查询：查询从 1 到 i 的前缀和。 
    i -= LSB(i)

树状数组的实现

初始化

将输入数组的值逐个更新到树状数组中。

代码实现：

public class FenwickTree {
    private int[] BIT; // 树状数组
    private int n;     // 数组大小

    public FenwickTree(int size) {
        n = size;
        BIT = new int[n + 1]; // 树状数组索引从 1 开始
    }

    // 单点更新，将索引 i 的值增加 delta
    public void update(int i, int delta) {
        while (i <= n) {
            BIT[i] += delta;
            i += i & -i; // 前进到下一个包含 i 的区间
        }
    }

    // 查询前缀和，从 1 到 i
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += BIT[i];
            i -= i & -i; // 回退到上一个区间
        }
        return sum;
    }

    // 查询区间 [l, r] 的和
    public int queryRange(int l, int r) {
        return query(r) - query(l - 1);
    }
}

示例运行

输入数组

int[] arr = {1, 3, 5, 7, 9, 11};

初始化

FenwickTree ft = new FenwickTree(arr.length);
for (int i = 0; i < arr.length; i++) {
    ft.update(i + 1, arr[i]); // 初始化树状数组
}

树状数组的内容（索引从 1 开始）：

BIT = [0, 1, 4, 5, 16, 9, 20]

查询前缀和

查询索引 1 到 4 的前缀和：

System.out.println(ft.query(4)); // 输出 16

区间查询

查询区间 [2, 5] 的和：

System.out.println(ft.queryRange(2, 5)); // 输出 24

单点更新

将索引 3 的值增加 2：

ft.update(3, 2); // 更新后，arr[3] = 7

更新后树状数组内容：

BIT = [0, 1, 4, 7, 18, 9, 20]

查询更新后的前缀和：

System.out.println(ft.query(4)); // 输出 18

树状数组的时间复杂度

  1. 单点更新：每次更新沿着树状数组的路径向上，最多进行 (O(\log n)) 次操作。
  2. 前缀查询：每次查询沿着树状数组的路径向下，最多进行 (O(\log n)) 次操作。
  3. 区间查询：通过两次前缀查询完成，时间复杂度为 (O(\log n))。

优点和局限性

优点

  1. 易于实现，代码量小。
  2. 时间复杂度低，适合频繁的动态查询和更新。

局限性

  1. 仅支持前缀和相关的操作。
  2. 对于复杂操作（如区间更新和区间查询），需要改进（如带懒惰标记的树状数组）。

总结

树状数组是一种高效的数据结构，用于处理动态数组的前缀和查询和单点更新。

其核心公式基于最低有效位，能够快速定位和更新相关区间信息，非常适合在在线算法和竞赛中使用。

为什么 BIT 可以提升性能，核心原理是什么？

树状数组（Binary Indexed Tree, BIT）能够提升性能的核心原理在于它的高效的前缀和查询和更新操作，可以将这些操作的时间复杂度降低到 O(log n)，从而在处理多个查询时显著提高效率。

1. 树状数组的结构

树状数组是一种基于二进制的数组结构，它可以在一个一维数组上模拟出一棵树，支持两个操作：

  • 更新操作（Update）：更新某个位置的值。

  • 查询操作（Query）：查询前缀和，即从数组的开头到某个位置的所有元素之和。

2. 核心原理

a) 前缀和的高效查询

树状数组通过在数组中存储部分前缀和来加速查询过程。

每个树状数组节点不存储整个数组的前缀和，而是存储某些区间的和，这样可以通过二进制拆分来加速查询。

  • 假设数组 arr 有 8 个元素，我们用树状数组来管理这些元素。

树状数组的节点存储了以下内容：

  • 索引为 1 存储了 arr[1]；
  • 索引为 2 存储了 arr[1] + arr[2]；
  • 索引为 3 存储了 arr[3]；
  • 索引为 4 存储了 arr[1] + arr[2] + arr[3] + arr[4]；
  • 索引为 5 存储了 arr[5]，以此类推。

这种结构使得我们能够通过快速地合并这些部分和来获得完整的前缀和。

b) 更新操作的高效性

在树状数组中，更新某个位置的值时，只需要修改涉及该位置的几个树状数组节点。

具体来说，更新操作通过二进制的低位部分找到需要修改的节点，然后更新这些节点，时间复杂度是 O(log n)。

c) 二进制拆分与树状数组节点的关系

树状数组的关键思想是利用二进制拆分来处理前缀和：

  • 每个节点所管理的区间大小与二进制数字有关。

例如，节点 3 可能对应的是 arr[1] + arr[2]，节点 4 可能对应的是 arr[1] + arr[2] + arr[3] + arr[4]。

  • 利用这种关系，通过将查询区间拆分成几个较小的区间，我们可以在 O(log n) 时间内求得前缀和。

d) 查询操作如何加速

假设我们要查询从数组的起点到某个位置 i 的前缀和。

通过树状数组结构，我们可以从位置 i 开始，逐步“跳跃”到更低的索引，直到查询到完整的前缀和：

  • 从 i 向前查询时，我们跳过不必要的部分，即跳到它二进制表示中的前 1 位所对应的区间，直到查询到区间的和为止。

  • 这个过程最多需要 log n 次跳跃，因此查询操作的时间复杂度为 O(log n)。

3. 树状数组如何提升性能

树状数组可以在多次更新和查询中显著提高效率的原因是：

  • 更新操作：更新树状数组的某个元素时，时间复杂度为 O(log n)，而不像直接操作数组那样需要线性扫描。通过不断更新树状数组的节点，可以高效地维持动态数据。

  • 查询操作：查询前缀和时，时间复杂度为 O(log n)，这是由于树状数组结构允许我们通过二进制拆分来减少查询区间的大小，而不是在数组中逐个元素累加。

对于一个包含多个查询的场景，树状数组通过 O(log n) 的时间复杂度使得每个查询变得高效，尤其在多次查询的情况下，与暴力 O(n) 查询相比，性能上得到了显著提升。

4. 总结

树状数组之所以能提高性能，关键在于它利用了部分前缀和的巧妙存储和二进制拆分，从而实现了更新和查询的对数时间复杂度。

这使得在处理大量数据和多次查询时，相较于暴力算法显著提高了效率。