树状数组（Fenwick / BIT）
数据结构 · lowbit 链 · 改查双 O(log n)
改与查的两难
要频繁地「单点加」和「求前缀和」：普通数组改 O(1) 查 O(n)；前缀和数组查 O(1) 改 O(n)——两头总有一头是 O(n)。树状数组用一行位运算魔法两头兼得：lowbit(i) = i & -i（取出 i 二进制的最低位 1）。
管辖区间：每个格子管一段
tree[i] 存「以 i 结尾、长度 lowbit(i)」那段的和：tree[4]（100₂，lowbit=4）管 a₁..a₄，tree[6]（110₂，lowbit=2）只管 a₅+a₆。query(6)：沿 i -= lowbit(i) 往前跳（6 → 4 → 0），两块拼出前缀和；update(3, +2)：沿 i += lowbit(i) 往后跳（3 → 4 → 8），把每个「管到 a₃」的区段都通知一遍——注意柱子当场长高。跳几步？i 的二进制位数——O(log n)。右侧代码随每一步同步高亮。
8 根柱子是 tree[1..8]，不是原数组：tree[i] 管辖「以 i 结尾、长 lowbit(i) = i & -i」的区段和——tree[4]=11 管 a₁..a₄、tree[6]=6 只管 a₅+a₆、tree[8]=21 管全部。两种操作都只沿 lowbit 链跳 O(log n) 步
1class BIT {
2 tree: number[]; // tree[i] 管辖长 lowbit(i) 的区段和
3 constructor(n: number) { this.tree = new Array(n + 1).fill(0); }
4 lowbit(i: number) { return i & -i; } // 最低位的 1
5 query(i: number): number { // 前缀和 a[1..i]
6 let s = 0;
7 for (; i > 0; i -= this.lowbit(i)) // 沿链往前跳
8 s += this.tree[i];
9 return s;
10 }
11 update(i: number, d: number) { // a[i] += d
12 for (; i < this.tree.length; i += this.lowbit(i))
13 this.tree[i] += d; // 通知每个管辖者
14 }
15}
原数组 a[3, 2, 5, 1, 4, 2, 3, 1]
读法tree[i] 管辖长 lowbit(i)
1 / 9
十行代码的性价比
三方案对比：数组（改 O(1)/查 O(n)）、前缀和（改 O(n)/查 O(1)）、BIT（双 O(log n)）。
lowbit 直觉：i 的二进制每去掉一个最低位 1，就吞并一段更靠前的区间。
区间和：query(r) − query(l−1)；区间加单点查用差分 BIT。
经典应用：逆序对计数、动态第 k 小（配倍增）、滑动统计。
lowbit 直觉：i 的二进制每去掉一个最低位 1，就吞并一段更靠前的区间。
区间和：query(r) − query(l−1)；区间加单点查用差分 BIT。
经典应用：逆序对计数、动态第 k 小（配倍增）、滑动统计。
与线段树相比：线段树全能（区间改/区间查/最值），BIT 只做前缀可加信息——但十行代码、常数小一半，覆盖日常 90% 的场景。竞赛里「能 BIT 不线段树」是常识；这也是数据结构大类的第 16 块拼图：数组结构从静态查询走到了动态统计。