core · 树状数组 BIT

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

树状数组 (Fenwick tree / Binary Indexed Tree) 解决前缀和「修改 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]$ 一整段。下图每根横杠就是一个 tree[i] 罩住的区间——长杠在上、短杠在下，这就是「树」的由来。

1 · 为什么 query 沿 $i -= lowbit(i)$ 往左跳就对了？

tree[i] 管的是 $(i-lowbit(i), i]$ 。把它采用后，还差前面 $a[1 .. i-lowbit(i)]$ 没算—— 而那正好是 $query(i - lowbit(i))$ 要算的前缀！于是「减掉最低位的 1」就是不重不漏地跳到左邻那一大段。每跳一次至少消掉二进制里的一个 1，而 i 最多有 $\log _2 n$ 个 1 → 最多 $O(\log n)$ 步。单步时注意看：被访问的那几段首尾相接，恰好平铺成 [1, i]。

2 · 为什么 update 沿 `i += lowbit(i)` 往上爬？

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

3 · 集合视角：为什么 update(a) 与 query(b) 不重不漏地对得上

把 update 与 query 各自走过的下标看成两个集合：up(a) = update(a) 从 a 一路 +lowbit 往上爬经过的下标； down(b) = query(b) 从 b 一路 $-lowbit$ 往左跳到 0 经过的下标。调 a、b 看这两条链—— 黄色格子是它们的唯一相遇点（格子上方/下方分别是十进制值与 5 位二进制）。

定理（相遇唯一性）： 对任意正整数 a、b——若 $a \le b$ ,up(a) 与 down(b) 恰好相遇一个下标; 若 a > b，两者无交集。直观上 up(a) 单调增、down(b) 单调减，二者必在 a 与 b 的最高不同二进制位处相遇，且仅此一次。这正是树状数组「改一个点、查一整段」全程不重不漏的根： $a \le b$ 时 a[a] 的改动被 query(b) 经由那个相遇节点统计恰好一次, a > b 时 a[a] 不在前缀 [1,b] 内，一次都不会被算进 query(b)。

4 · 插曲：`lowbit(i) = i & (−i)` 为什么恰好取出最低位的 1

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

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 次加法。

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]

区间改 + 区间查：再开一个 BIT 维护 $i\cdot d[i]$ ，则前缀和 sum(1, r) = (r+1)·Σ_{i≤r} d[i] − Σ_{i≤r} i·d[i]，两个前缀各 $O(\log n)$ ，区间和用 $sum(1,r) - sum(1,l-1)$ 。区间修改仍只在两个 BIT 上各 update 两下——修改与查询双双 $O(\log n)$ ，功能上追平线段树 + lazy 的「区间加 + 区间和」，而常数更小。

下面这个 lab 跑的就是两个 BIT 的「区间加 + 区间和」。区间加 [l,r]+=v 在差分上只动两个端点 l 与 r+1, 于是在 B1(d) 与 $B2(i\cdot d)$ 上各 update 两处（绿色 = 本次被改的格）；区间和按 $(x+1)\cdot B1(x) - B2(x)$ 取两个前缀（黄色 = 本次被读的格），再相减。每条 BIT 内部沿 lowbit 的爬升 / 回跳与本页主线 lab 完全一致，这里只看「两端点 × 两 BIT」与那条求和公式。

7 · 进阶：在树状数组上倍增二分，O(log n) 求第 k 小

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

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

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

下面在一张 6×6 的 tree[x][y] 网格上看它怎么动。单点改 (x,y)+=v：外层 x 沿 lowbit 往上爬、内层 y 也爬，被改的格是两条爬升的笛卡尔积（绿色），共 $\log m \times \log n$ 个——这就是「套两层」。 前缀矩形 query(x,y)：两维各往左下回跳，读取的格（黄色）也是笛卡尔积。任意矩形和则用四角容斥, 由 4 个左上角前缀矩形加减而来。

9 · 实际应用

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