树状数组（BIT）：轻量的前缀结构
基于通用算法套路 · 核于 2026-07
速查
- 本质：用一个普通数组
tree[1..n]（下标从 1 开始）编码一棵隐式二叉树，每个tree[i]管辖区间[i - lowbit(i) + 1, i]，靠lowbit决定管的长度。 - lowbit：
lowbit(x) = x & (-x)，取 x 二进制最低位的 1 及其后的 0。例lowbit(6) = lowbit(0b110) = 0b10 = 2。 - tree[i] 管辖区间：长度为
lowbit(i)，从i - lowbit(i) + 1到i（含两端）。i 末尾 0 越多（lowbit 越大）管得越长。 - 单点修改
add(i, v)：把a[i] += v，沿i += lowbit(i)一路上传更新所有覆盖 i 的tree节点——O(log n)。 - 前缀查询
query(i)：求a[1] + ... + a[i]，沿i -= lowbit(i)一路累加——O(log n)。 - 区间查询：
sum(l, r) = query(r) - query(l - 1)，两前缀相减。 - 复杂度：建树 O(n) 或 O(n log n)；单点改 / 前缀查 / 区间查 全是 O(log n)；空间 n+1。
- vs 线段树：树状数组常数更小（迭代无递归、缓存友好）、代码更短（~20 行）、空间更省（n+1 vs 4n）；但只支持单点改 + 前缀查，原生不支持区间修改。
- 区间修改的差分技巧：维护差分数组的树状数组，可实现「区间加 + 单点查」；维护二级前缀可实现「区间加 + 区间查」——但只对加法有效，不如线段树通用。
- 经典应用：逆序对（BIT 扫描计数）、动态前缀和、最长上升子序列 O(n log n)（BIT 优化 DP）、离散化后求排名。
- 限制：维护的信息需满足结合律且可逆（能
a - b还原），如和、异或；求最值不可逆，BIT 难维护。 - 交互演示：树状数组可视化。
一、lowbit：二进制最低位的 1
lowbit(x) 取 x 的二进制表示中最低位的 1 及其后的 0 组成的数。计算用位运算：
function lowbit(x) {
return x & (-x); // 等价于 x & (~x + 1)
}原理：-x 是 x 的补码（取反加一），与 x 相与恰好保留最低位的 1。举例（n=8）：
i (十进制) | 二进制 | lowbit(i) | tree[i] 管辖区间
1 | 0001 | 1 | [1,1]
2 | 0010 | 2 | [1,2]
3 | 0011 | 1 | [3,3]
4 | 0100 | 4 | [1,4]
5 | 0101 | 1 | [5,5]
6 | 0110 | 2 | [5,6]
7 | 0111 | 1 | [7,7]
8 | 1000 | 8 | [1,8]规律：i 二进制末尾 0 的个数 = lowbit 的指数。lowbit(8) = 8（管整个 [1,8]），lowbit(4)=4（管 [1,4]），lowbit(6)=2（管 [5,6]）。
二、tree[i] 管辖的区间
定义：tree[i] 管辖区间 [i - lowbit(i) + 1, i]，长度 lowbit(i)。这个定义编码了一棵隐式二叉树——tree[8]（lowbit=8）是根管 [1,8]，它的「左孩子」tree[4]（lowbit=4）管 [1,4]、「右孩子」tree[12]（lowbit=4）管 [9,12]，以此类推。
注意几个关键点：
- 下标从 1 开始：
tree[0]无定义（lowbit(0)=0会死循环）。所以树状数组要开n+1长度，a 和 tree 下标都从 1 算起（原数组a[0..n-1]对应 tree 的1..n）。 - 覆盖关系：
tree[i]管[i-lowbit(i)+1, i]；而覆盖i的所有节点 = 沿i += lowbit(i)一直往上的序列（修改路径）。
三、核心操作：O(log n) 的单点改与前缀查
单点修改 add(i, v)：a[i] += v
把 a[i] 加 v 后，所有覆盖 i 的 tree 节点都要加 v。覆盖 i 的节点序列是 i, i+lowbit(i), i+lowbit(i+lowbit(i)), ...——每次 i += lowbit(i) 跳到上一层。
function add(i, v, n) { // i 从 1 开始
for (; i <= n; i += lowbit(i)) {
tree[i] += v;
}
}直觉：i += lowbit(i) 把 i 末尾那个 1 进位（如 0110 + 0010 = 1000），跳到管更大区间的祖先节点。
前缀查询 query(i)：求 a[1] + ... + a[i]
前缀 [1, i] 可以被拆成若干个 tree 节点的并：从 i 出发，每次取 tree[i]（管 [i-lowbit(i)+1, i]），然后 i -= lowbit(i) 跳到前一段。
function query(i) { // i 从 1 开始
let sum = 0;
for (; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}直觉：i -= lowbit(i) 抹掉 i 末尾的 1（如 0110 - 0010 = 0100），跳到管前一段的节点。
为什么是 O(log n)：每次 i += lowbit(i) 或 i -= lowbit(i) 都改变 i 的二进制位数，i 最多有 ⌈log₂n⌉ 位，所以循环至多 O(log n) 次。
区间查询：两前缀相减
function rangeSum(l, r) { // [l, r] 闭区间，从 1 开始
return query(r) - query(l - 1);
}四、建树
最朴素：n 次 add，O(n log n)。更快的 O(n) 方法：直接按区间定义累加。
// O(n log n) 简单版
function build(a, n) {
for (let i = 1; i <= n; i++) add(i, a[i], n);
}
// O(n) 版：tree[i] = a[i-lowbit(i)+1] + ... + a[i]
function buildLinear(a, n) {
for (let i = 1; i <= n; i++) {
tree[i] = a[i];
for (let j = i - lowbit(i) + 1; j < i; j++) tree[i] += a[j];
}
}五、区间修改的差分技巧（区间加 + 单点查）
树状数组原生只支持单点改。但维护差分数组 d[i] = a[i] - a[i-1]，可实现「区间加 + 单点查」：
- 区间
[l, r]加 v：add(l, v); add(r+1, -v)（差分套路）。 - 查
a[i]：a[i] = d[1] + ... + d[i] = query(i)（差分的前缀和 = 原数组）。
// 区间 [l, r] 加 v
function rangeAdd(l, r, v, n) {
add(l, v, n);
if (r + 1 <= n) add(r + 1, -v, n);
}
// 查单点 a[i]
function pointQuery(i) {
return query(i); // 差分数组的前缀和
}要实现「区间加 + 区间查」，需维护 d[i] 和 i×d[i] 两个 BIT（推导略），不如线段树通用。所以需要区间修改 + 区间查询时，直接上线段树更省心。
六、与线段树对比
| 维度 | 树状数组（BIT） | 线段树 |
|---|---|---|
| 单点改 + 区间查 | O(log n)，常数小 ✅ | O(log n) |
| 区间改 + 区间查 | 差分技巧（仅加法） | 原生支持（懒标记） ✅ |
| 维护信息 | 需结合律且可逆 | 任意满足结合律 |
| 代码量 | ~20 行 ✅ | ~100 行（含 lazy） |
| 空间 | n+1 ✅ | 4n |
| 常数 | 极小（迭代） ✅ | 较大（递归） |
选型：只做单点改 + 前缀/区间查 → BIT（更快更短）；要区间改 + 区间查、或维护不可逆信息（最值）→ 线段树。
七、经典应用
求逆序对（BIT 扫描计数）
逆序对：i < j 但 a[i] > a[j]。从左到右扫，每来一个 a[j]，问「前面有多少个数比 a[j] 大」= 已插入总数 - query(a[j])，累加即为逆序对数。值域大时先离散化（把 a 映射到排名 1..n）。
// a 已离散化到 [1, n]
let inv = 0;
for (let j = 0; j < n; j++) {
inv += (j) - query(a[j]); // j 是已插入个数
add(a[j], 1, n);
}LIS 最长上升子序列 O(n log n)
dp[i] = 长度为 i 的上升子序列的最小末尾。BIT 优化：f[x] = 以值 x 结尾的 LIS 长度，f[x] = max(f[1..x-1]) + 1，用 BIT 维护前缀 max。
八、易错点
- 下标从 0 开始：树状数组必须从 1 开始（lowbit(0)=0 死循环）。原数组
a[0..n-1]要映射到tree[1..n]，即代码里i用原下标 + 1。 - 忘离散化：值域大（如 10⁹）时直接开 BIT 数组会爆内存，必须先离散化到
[1, n]。 - 区间加忘
r+1判越界：add(r+1, -v)时r+1可能等于n+1超出，要if (r+1 <= n)。 - 维护最值用 BIT：BIT 维护最值（不可逆）很麻烦，区间修改时无法正确更新——直接用线段树。
- 建树用 add 导致 O(n log n)：对 n 大的题可能 TLE，用 O(n) 版。
交互演示
- 树状数组可视化演示 —— lowbit 跳跃、tree[i] 管辖区间与单点改/前缀查过程
下一步
线段树与树状数组的原理都讲完了。最后看两者的代码模板、复杂度对比与选型决策——一页速查，见参考。