无解的博客

Appearance

wxvirus2026-06-09
2146
9.5m

树状数组（Binary Indexed Tree） ​

假设你在做一个实时排行榜系统，用户不断提交分数，你需要随时回答："排名第 k 的选手，他的总分是多少？" 换句话说，就是不断地单点更新和前缀和查询。

用普通数组？每次求前缀和都要 O(n)，如果用户有 100 万，每次查询都要遍历一遍，太慢了。 用前缀和数组？查询 O(1) 了，但每次更新一个点，后面所有前缀和都要改，更新 O(n)，还是不行。

有没有一种数据结构，能让更新和查询都是 O(log n)？

有！它就是树状数组（Binary Indexed Tree，简称 BIT），也叫 Fenwick Tree。它用一个非常巧妙的位运算技巧，把前缀和查询拆成了"几个跳跃"，代码量极短（核心就十几行），但思想非常精妙 ✨。

为什么需要树状数组？ ​

先明确一下问题场景。我们有一个数组 arr[1..n]，需要支持两种操作：

1. update(i, delta)  → 把 arr[i] 增加 delta
2. query(i)          → 求 arr[1] + arr[2] + ... + arr[i]（前缀和）

三种方案的对比：

方案updatequery空间
普通数组O(1)O(n)O(n)
前缀和数组O(n)O(1)O(n)
树状数组O(log n)O(log n)O(n)

树状数组在频繁更新 + 频繁查询的场景下，是性价比最高的选择。

当然还有线段树也能做，而且功能更强（支持区间更新、区间查询），但树状数组的代码量只有线段树的 1/3，面试手写更容易写对。

原理拆解 ​

核心思想：lowbit ​

树状数组的灵魂就一个操作——lowbit，取一个数二进制表示中最低位的 1：

typescript
function lowbit(x: number): number {
  return x & (-x);
}

举几个例子：

lowbit(6)  = lowbit(0b110)   = 0b010 = 2
lowbit(8)  = lowbit(0b1000)  = 0b1000 = 8
lowbit(12) = lowbit(0b1100)  = 0b0100 = 4
lowbit(7)  = lowbit(0b0111)  = 0b0001 = 1

-x 在补码下等于 ~x + 1，和 x 做 & 操作，刚好留下最低位的 1。这个技巧记住就好，不需要深究。

树状数组长什么样？ ​

树状数组用一个数组 tree[] 来维护信息，其中 tree[i] 管理的是一段连续区间的和：

tree[i] 管理的区间：[i - lowbit(i) + 1, i]

具体来说：
tree[1] = arr[1]                          管 1 个元素
tree[2] = arr[1] + arr[2]                 管 2 个元素
tree[3] = arr[3]                          管 1 个元素
tree[4] = arr[1] + arr[2] + arr[3] + arr[4]  管 4 个元素
tree[5] = arr[5]                          管 1 个元素
tree[6] = arr[5] + arr[6]                 管 2 个元素
tree[7] = arr[7]                          管 1 个元素
tree[8] = arr[1] + ... + arr[8]           管 8 个元素

画成树的结构更直观：

            tree[8] = arr[1..8]
           /        \
    tree[4]=arr[1..4]  tree[6]=arr[5..6]  tree[7]=arr[7]
    /        \             /        \
 tree[2]   tree[3]     tree[5]    tree[6]
  /  \
t[1] t[2]

每个节点的父节点 = i + lowbit(i)
例如：tree[2] 的父节点 = 2 + lowbit(2) = 2 + 2 = 4
例如：tree[5] 的父节点 = 5 + lowbit(5) = 5 + 1 = 6

操作详解 ​

前缀和查询 query(i) ​

要求 arr[1] + arr[2] + ... + arr[i]，就是从 tree[i] 开始，每次跳到 i - lowbit(i)，把沿途的 tree 值加起来：

query(7) = tree[7] + tree[6] + tree[4]
         = arr[7] + (arr[5]+arr[6]) + (arr[1]+arr[2]+arr[3]+arr[4])
         = arr[1..7] ✅

跳的过程：
  i=7 → 取 tree[7]，跳到 7 - lowbit(7) = 6
  i=6 → 取 tree[6]，跳到 6 - lowbit(6) = 4
  i=4 → 取 tree[4]，跳到 4 - lowbit(4) = 0
  i=0 → 停止

单点更新 update(i, delta) ​

把 arr[i] 增加 delta，需要更新所有管辖了 arr[i] 的 tree 节点。这些节点是 i, i+lowbit(i), i+lowbit(i)+lowbit(...)，一直往上跳到超出范围：

update(3, +5) 的影响路径：
  i=3 → 更新 tree[3]，跳到 3 + lowbit(3) = 4
  i=4 → 更新 tree[4]，跳到 4 + lowbit(4) = 8
  i=8 → 更新 tree[8]，跳到 8 + lowbit(8) = 16
  ...直到超出 n

所以 tree[3], tree[4], tree[8] 都会被更新，因为它们都包含了 arr[3]

代码实现 ​

TypeScript 实现 ​

typescript
class BinaryIndexedTree {
  private tree: number[];
  private n: number;

  constructor(size: number) {
    this.n = size;
    this.tree = new Array(size + 1).fill(0);
  }

  /** lowbit：取最低位的 1 */
  private lowbit(x: number): number {
    return x & (-x);
  }

  /** 单点更新：把 index 位置增加 delta（1-indexed） */
  update(index: number, delta: number): void {
    for (let i = index; i <= this.n; i += this.lowbit(i)) {
      this.tree[i] += delta;
    }
  }

  /** 前缀和查询：求 arr[1..index] 的和（1-indexed） */
  query(index: number): number {
    let sum = 0;
    for (let i = index; i > 0; i -= this.lowbit(i)) {
      sum += this.tree[i];
    }
    return sum;
  }

  /** 区间和查询：求 arr[left..right] 的和 */
  rangeQuery(left: number, right: number): number {
    return this.query(right) - this.query(left - 1);
  }
}

用法示例：

typescript
const bit = new BinaryIndexedTree(10);

// 建立初始数组 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
for (let i = 0; i < arr.length; i++) {
  bit.update(i + 1, arr[i]); // 1-indexed
}

console.log(bit.query(5));       // 3+1+4+1+5 = 14
console.log(bit.rangeQuery(3, 7)); // 4+1+5+9+2 = 21

// 把第 4 个元素（值为 1）增加 10，变成 11
bit.update(4, 10);
console.log(bit.query(5));       // 3+1+4+11+5 = 24

Python 实现 ​

python
class BinaryIndexedTree:
    def __init__(self, size: int):
        self.n = size
        self.tree = [0] * (size + 1)

    def lowbit(self, x: int) -> int:
        return x & (-x)

    def update(self, index: int, delta: int) -> None:
        i = index
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)

    def query(self, index: int) -> int:
        total = 0
        i = index
        while i > 0:
            total += self.tree[i]
            i -= self.lowbit(i)
        return total

    def range_query(self, left: int, right: int) -> int:
        return self.query(right) - self.query(left - 1)

从原数组建树的两种方式 ​

方式一：逐个 update（上面的写法） ​

typescript
for (let i = 0; i < n; i++) {
  bit.update(i + 1, arr[i]);
}
// 时间复杂度：O(n log n)

方式二：O(n) 线性建树 ​

利用一个巧妙的递推：tree[i] 可以从它直接管辖的子区间累加得到：

typescript
function build(arr: number[]): BinaryIndexedTree {
  const n = arr.length;
  const bit = new BinaryIndexedTree(n);
  // 先把原数组复制进去
  for (let i = 0; i < n; i++) {
    bit['tree'][i + 1] = arr[i];
  }
  // 对每个位置，把它的值累加到父节点
  for (let i = 1; i <= n; i++) {
    const parent = i + bit['lowbit'](i); // 不对，需要直接操作
    // 更好的写法：
  }
  return bit;
}

其实实际面试和刷题中，O(n log n) 的建树方式完全够用，不用纠结这个优化。

复杂度分析 ​

操作时间复杂度说明
单点更新O(log n)最多跳 log n 层
前缀和查询O(log n)最多跳 log n 层
区间和查询O(log n)两次前缀和相减
建树O(n log n)n 次 update
空间O(n)一个长度为 n+1 的数组

实际应用 ​

应用一：动态逆序对计数（LeetCode 315） ​

给一个数组，对每个位置 i，求它右边有多少个比 arr[i] 小的元素。

思路：从右往左遍历，用树状数组维护已遍历元素的频次。对于当前元素 x，查询 query(x-1) 就是右边比 x 小的元素个数。

typescript
function countSmaller(nums: number[]): number[] {
  // 离散化（把值映射到 1..n）
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  sorted.forEach((v, i) => rank.set(v, i + 1));

  const n = nums.length;
  const bit = new BinaryIndexedTree(sorted.length);
  const result: number[] = new Array(n);

  for (let i = n - 1; i >= 0; i--) {
    const r = rank.get(nums[i])!;
    result[i] = r > 1 ? bit.query(r - 1) : 0;
    bit.update(r, 1);
  }
  return result;
}

应用二：区间求和 + 单点更新（LeetCode 307） ​

设计一个数据结构，支持修改数组中某个元素的值，以及求某个区间的和。

这基本上就是树状数组的教科书用法，直接套模板就行。

应用三：统计小于某个值的元素个数 ​

在离线查询场景下，可以用树状数组做"桶计数"：遍历查询，把元素按值插入树状数组，然后 query(k) 就是值 ≤ k 的元素个数。

树状数组 vs 线段树 ​

特性树状数组线段树
代码量~15 行~80 行
空间O(n)O(4n)
单点更新✅ O(log n)✅ O(log n)
区间更新（懒标记）❌（需要差分技巧）✅ O(log n)
区间查询只能前缀和✅ 任意区间
调试难度低高

面试建议：如果题目只需要单点更新 + 前缀和/区间和，优先用树状数组，代码短、写得快、不容易出错。如果需要区间更新或更复杂的区间操作（最大值、最小值等），再上线段树。

总结 ​

树状数组就是一个用位运算 lowbit 技巧来管理前缀和的精妙数据结构：

  1. lowbit(x) = x & (-x) 取最低位 1，这是整个算法的灵魂
  2. 查询从 i 往左跳（i -= lowbit(i)），累加沿途 tree 值
  3. 更新从 i 往右跳（i += lowbit(i)），更新沿途 tree 值
  4. 两者都是 O(log n)，代码量极小

下次遇到"频繁单点修改 + 频繁前缀查询"的题目，别犹豫，直接上树状数组 🎯

最近更新