core · 树状数组 BIT

树状数组：用 lowbit 把数组叠成一棵隐形的树

树状数组（Fenwick tree / Binary Indexed Tree）[1] 解决前缀和「修改 O(n)」的瓶颈：让单点修改和前缀和查询 都只要 $O(\log n)$ 。它不另建一棵真的树，而是用一个同样大小的数组 tree[], 靠一个位运算 lowbit(i) = i & (−i) 隐式地组织出树形结构。

注 · 核心约定是 1-indexed。tree[i] 负责原数组的一段—— 区间 $(i - lowbit(i), i]$ ，长度恰好等于 lowbit(i)（i 二进制最低位的 1 的权重）。
比如 lowbit(6)=lowbit(0b110)=2 → tree[6] 管 $a[5..6]$ ; lowbit(8)=8 → tree[8] 管 $a[1..8]$ 一整段。下标必须从 1 起： $\mathrm{lowbit}(0) = 0$ ，一旦让 0 进入 i += lowbit(i) 就会原地死循环。

图 0-1 · 每根横杠是一个 tree[i] 罩住的区间，长杠在上、短杠在下。可单步执行 update 与 query，观察各自走过的下标。

1 · query 向左跳的依据

注 · tree[i] 管的是 $(i - \mathrm{lowbit}(i),\, i]$ 。把它计入后，还差前面的 $a[1 \dots i-\mathrm{lowbit}(i)]$ 没算，而那正好是 $\mathrm{query}(i - \mathrm{lowbit}(i))$ 要算的前缀，于是「减掉最低位的 1」就是不重不漏地跳到左邻那一大段。每跳一次至少消掉二进制里的一个 1，而 $i$ 最多有 $\lfloor \log_2 n \rfloor + 1$ 个 1，故最多 $O(\log n)$ 步。被访问的那几段首尾相接，恰好平铺成 $[1, i]$ 。

2 · update 向上爬的依据

注 · 改了 $a[i]$ ，所有区间包含 $i$ 的 tree[j] 都得跟着加。可以证明这些 $j$ 恰好构成序列 $i,\ i + \mathrm{lowbit}(i),\ \dots$ 一直到 $n$ ，每次「进位」到上一层更长的那根杠，同样最多 $O(\log n)$ 步。区间和则用两个前缀相减： $\mathrm{sum}(l, r) = \mathrm{query}(r) - \mathrm{query}(l-1)$ 。

3 · 两条链的唯一相遇点

把 update 与 query 各自走过的下标看成两个集合：up(a) = update(a) 从 a 一路 +lowbit 往上爬经过的下标； down(b) = query(b) 从 b 一路 $-lowbit$ 往左跳到 0 经过的下标。

图 3-1 · up(a) 与 down(b) 两条链的唯一相遇点。可调

a

与

b

，黄色格子即相遇点，格子上下分别是十进制值与 5 位二进制。

定理 3.1（相遇唯一性） 对任意 $1 \le a, b \le n$ ：若 $a \le b$ ， $\mathrm{up}(a)$ 与 $\mathrm{down}(b)$ 恰好相遇一个下标；若 $a > b$ ，两者无交集。

相遇点可以直接读出来： $\mathrm{query}(b)$ 拆出的那几段恰好平铺 $[1, b]$ ， $a \le b$ 时 $a$ 必落在其中唯一一段里，那一段的节点就是相遇点。这正是树状数组「改一个点、查一整段」全程不重不漏的根据—— $a \le b$ 时 $a[a]$ 的改动经由那个相遇节点被统计恰好一次， $a > b$ 时 $a[a]$ 不在前缀 $[1, b]$ 内，一次都不会被算进去。

用位运算刻画相遇点要当心： $a$ 与 $b$ 的最高不同二进制位给出的不是相遇点。 $1 \le a \le b \le 64$ 共 2080 组里有 129 组不符，最小反例是 $a = 2$ 、 $b = 3$ ——实际相遇于 2，而按 $a \oplus b$ 构造得到 3。改用 $(a-1) \oplus b$ 的最高位则 2080 组全中，根因是 tree[j] 覆盖的是半开区间 $(j - \mathrm{lowbit}(j),\, j]$ ，左端点落在 $a-1$ 那一侧。

4 · lowbit 的推导

前面一直在用 lowbit，本节给出完整推导。计算机用补码（two's complement）表示负数： $-i = \lnot i + 1$ ，即按位取反再加 1。取反把 i 最低位的那个 1 变成 0、其右侧的 0 全变 1；随后 +1 的进位一路填到那个位为止，使它复原为 1，而它左侧所有位与原来恰好相反。于是 i 与 $-i$ 唯一相同的就是「最低位的 1 及其右侧的 0」，按位与一过只剩那一个 1——这就是 lowbit。

图 4-1 · lowbit(i) = i & (−i) 的逐位演示。可改

i

，观察取反加一后与原值按位与只剩最低位那个 1。

5 · 建树：从 O(n log n) 的逐个插入到 O(n) 的线性建法

最直白的建树是把每个 $a[i]$ 当一次 update 灌进去：n 次、每次 $O(\log n)$ → O(n log n) （本页顶部 demo 的 rebuild() 就是这版，数据量小无所谓）。但有一个 O(n) 的线性建法：先令每个 tree[i] = a[i]，再从小到大让每个节点把已经累好的整段「上交」给它的父亲 i + lowbit(i)。轮到 i 时，落在它负责区间内的贡献都已并入 tree[i]，一次加法即整段交付；每个节点只被其唯一父亲收一次 → 全程 n 次加法。

图 5-1 ·

O(n)

线性建树的代码骨架：先令 tree[i] = a[i]，再按下标升序把每格并进它的父格。

6 · 四象限：用差分把「单点改」升级成「区间改」

本页主线 BIT 解决的是「单点改 + 区间查」这一格。把维护对象从原数组换成它的差分数组 $d[i] = a[i] - a[i-1]$ ，就能补齐「区间改」的两格——因为「区间 [l,r] 整体加 d」落在差分上只是两个端点的单点改。

	单点查 a[i]	区间查 sum(l, r)
单点改	直接用数组，O(1)	本页主线 BIT:query(r) − query(l−1)
区间改	差分 BIT：改 2 下，查 = 前缀和	两个 BIT：维护 d[i] 与 i·d[i]

图 6-1 · 差分数组上「区间加、单点查」的代码骨架。

建议 · 区间改配区间查：再开一个 BIT 维护 $i\,d[i]$ ，则前缀和 $\mathrm{sum}(1, r) = (r+1)\sum_{i \le r} d[i] - \sum_{i \le r} i\,d[i]$ ，两个前缀各 $O(\log n)$ ，区间和用 $\mathrm{sum}(1, r) - \mathrm{sum}(1, l-1)$ 。区间修改在两个 BIT 上各至多 update 两处（ $r = n$ 时 $r+1$ 越界，只动左端点一处），修改与查询双双 $O(\log n)$ ，功能上追平线段树加 lazy 的「区间加 + 区间和」，常数更小。

区间加 $[l, r] \mathrel{+}= v$ 在差分上只动两个端点 $l$ 与 $r+1$ ，于是在两个 BIT 上各至多 update 两处；区间和按 $(x+1)B_1(x) - B_2(x)$ 取两个前缀再相减。每条 BIT 内部沿 lowbit 的爬升与回跳和图 0-1 完全一致。

图 6-2 · 两个 BIT 协作完成「区间加 + 区间和」。绿色是本次被改的格、黄色是本次被读的格；

r = n

时右端点越界，只从左端点一处爬升。

7 · 权值 BIT 上的倍增二分

把 BIT 建在权值上（tree 维护「值 = v 的元素出现了几次」的前缀计数），就能回答「第 k 小的值是多少」。常规做法是「外层二分加每次一个前缀和」，共 $O(\log^2 n)$ ；更优的是直接在 BIT 上倍增：让 $pos$ 从 0 起，按 $j$ 从大到小试着往右跨 $2^j$ 。不变量是「轮到 $j$ 时 $pos$ 已是 $2^{j+1}$ 的倍数、低位全为 0」，于是 $\mathrm{lowbit}(pos + 2^j)$ 恰为 $2^j$ ，tree[pos + 2^j] 正好缓存 $(pos,\, pos+2^j]$ 这段的计数，一次比较就知道第 $k$ 小是否落在这一跨之外，全程只走 $O(\log n)$ 步。

图 7-1 · 权值 BIT 上倍增二分求第

k

小。可改计数与

k

，观察

pos

如何按

2^j

由大到小逐步右移。

8 · 升维：二维树状数组（单点改 + 矩形和）

应用页的二维前缀和是静态的——改一个点要重算一大片。把 BIT 套两层：外层下标走行、内层走列， tree[x][y] 对两维各负责一段 lowbit 区间，就得到可带修改的二维结构。单点改与矩形和都是 $O(\log m \cdot \log n)$ ；矩形和同样用二维容斥，把它拆成 4 个「左上角前缀矩形」之差。

图 8-1 · 二维树状数组的单点改与前缀矩形和的代码骨架。

单点改时外层 $x$ 沿 lowbit 往上爬、内层 $y$ 也爬，被改的格是两条爬升的笛卡尔积，至多 $(\lfloor\log_2 m\rfloor+1)(\lfloor\log_2 n\rfloor+1)$ 个；实际远少于这个上界，6×6 网格上实测触及格数在 1 到 9 之间、均值 3.36—— $(1,1)$ 处 9 格， $(4,4)$ 处只 1 格。前缀矩形查询时两维各往左下回跳，读取的格也是笛卡尔积；任意矩形和则由 4 个左上角前缀矩形四角容斥而来。

图 8-2 · 6×6 的二维 BIT 网格。绿色是单点改触及的格、黄色是前缀矩形读取的格，两者都是两维爬升的笛卡尔积。

9 · 实际应用

BIT 是竞赛与工程里「单点改 + 前缀或区间和」的常见首选：代码极短、常数极小、缓存友好。其前缀相减法要求聚合落在群上（可逆），min/max 这类没有逆元的聚合用不了它。经典用途：实时排行榜求名次（玩家上分后求「比我分高的有几人」= 后缀计数，游戏 / 竞价排名常用）、 动态求逆序对（边插入边数前面比它大的个数，衡量推荐序列错乱度）、区间第 k 小（权值 BIT / 树套树）、 风控里某时间窗的事件计数、配合差分做区间加 + 区间和。需要 min/max 等更复杂的聚合或区间赋值时，则使用线段树。

10 · 参考文献

Fenwick, P. M. (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience, 24(3), 327–336.