学习首页/数据结构/树状数组交互演示 · JavaScript

代码与动画 FENWICK TREE · BIT

树状数组.

利用 lowbit 管理累计区间，实现单点增量与前缀查询。

更新 / 查询 O(log n)空间 O(n)下标从 1 开始

原理与执行逻辑

树状数组用 lowbit 决定每个累计块覆盖的区间。更新时访问所有包含该位置的块，查询时把前缀拆成互不重叠的块相加。

执行步骤

  1. 使用从 1 开始的下标，计算 lowbit(i) = i & -i。
  2. 单点增加 delta 时更新 bit[i]，再令 i += lowbit(i) 继续向上。
  3. 查询前缀时累加 bit[i]，再令 i -= lowbit(i) 向前跳。
  4. 查询闭区间 [l, r] 可使用 sum(r) - sum(l - 1)。

关键理解

bit[i] 保存 [i - lowbit(i) + 1, i] 的和。更新方向寻找覆盖当前点的更大块，查询方向移除已计入的块；下标 0 不参与更新。

简短示例

bit[6] 覆盖 [5,6]，bit[4] 覆盖 [1,4]，因此 sum(6) = bit[6] + bit[4]；更新位置 5 会依次影响 5、6、8。

代码与执行动画

STEP 0 / 0
树状数组
function build(values) {  const bit = Array(values.length + 1).fill(0);  for (let i = 1; i <= values.length; i++) {    for (let j = i; j < bit.length; j += j & -j) bit[j] += values[i - 1];  }  return bit;}
7 行 · 0 个片段标记
上行 a · 下行 BITlowbit(i) = i & -i
2a[1]1a[2]3a[3]4a[4]2a[5]5a[6]1a[7]6a[8]2[1, 1]3[1, 2]3[3, 3]10[1, 4]2[5, 5]7[5, 6]1[7, 7]24[1, 8]
当前数据正在操作已访问 / 命中标记 / 指针
0

当前结构

选择操作，观察对应代码和状态变化。

操作当前结构

操作结果会用于下一次操作；重置结构恢复初始数据。

实现说明

树状数组的操作规则

上行是原数组，下行是 BIT；bit[i] 覆盖 [i - lowbit(i) + 1, i]。更新跳到 i + lowbit(i)，查询跳到 i - lowbit(i)。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。