树状数组的索引设计lowbit 不是魔法是二进制规律的直接推论一、lowbit 的魔法公式你只会背吗初学树状数组Fenwick Tree时最先要背的就是lowbit(x) x -x。这个公式看起来像黑魔法为啥 x 和 -x 做按位与就能得到最低位的 1 所代表的数值大多数题解到此为止——记住就行用就完了。但如果面试时被追问一句为什么这样设计能保证前缀和查询是 O(log n) 的只靠背公式是不够的。这篇文章会从二进制补码和索引规律出发推导出 lowbit 的数学来源进而解释为什么树状数组的单点更新和区间查询都是 O(log n)。flowchart TB A[树状数组 BIT] -- B[核心操作1: lowbit x] B -- C[x -x x 的最低位 1 代表的数] C -- D[索引规律] D -- E[BIT1 管理 a1] D -- F[BIT2 管理 a1,a2] D -- G[BIT4 管理 a1..a4] D -- H[BIT8 管理 a1..a8] E -- I[前缀和: 不断减 lowbit] F -- I G -- I H -- I I -- J[sum(7) BIT7 BIT6 BIT4] K[单点更新: 不断加 lowbit] -- L[update(3) → BIT3, BIT4, BIT8]二、lowbit 的二进制本质计算机使用补码表示负数。-x 的计算方式是将 x 按位取反后加 1-x ~x 1。例如 x 12二进制 1100。x 按位取反0011。加 10100。x -x 1100 0100 0100 4。lowbit(12) 4确实等于最低位 1 代表的数值二进制的 100。为什么这个按位与恰好能取到最低位的 1因为取反操作让低位全部变为 1加 1 后低位产生进位——这个进位会一直传播到第一个 0这个 0 恰好就是原来最低位 1 的位置。结果是x和-x只有这一位是公共的 1所以按位与后只保留这一位。树状数组的索引结构。BIT[i] 管理的区间长度 lowbit(i)。具体来说BIT[i] a[i - lowbit(i) 1] ... a[i]。例如 BIT[6] a[5] a[6]lowbit(6) 2BIT[4] a[1] a[2] a[3] a[4]lowbit(4) 4。前缀和查询不断减 lowbit。sum(7) BIT[7] BIT[6] BIT[4]。分解过程7 → lowbit(7)1 → 66 → lowbit(6)2 → 44 → lowbit(4)4 → 0。每次减掉 lowest bit 1最多 O(log n) 步。单点更新不断加 lowbit。更新 a[3] 需要更新 BIT[3]、BIT[4]、BIT[8]... 因为 lowbit(3)1 → 314lowbit(4)4 → 448。每一步都将最低位 1 进位到更高位。三、树状数组的完整实现与使用场景 树状数组Fenwick Tree——完整实现 功能单点更新 区间查询 应用场景逆序对计数、动态维护前缀和、离线二维偏序 from typing import List class FenwickTree: 树状数组 所有索引从 1 开始内部自动处理 为什么索引从 1 开始lowbit(0) 0会导致死循环。 def __init__(self, n: int): n: 数组长度 为什么数组大小是 n1索引 0 不使用 避免 lowbit(0) 0 导致的无限循环。 self.n n self.tree [0] * (n 1) staticmethod def lowbit(x: int) - int: 计算 x 的 lowbit 为什么用 x -x在补码表示下 -x ~x 1。x 与 ~x1 的按位与 恰好等于 x 中最低位 1 代表的数值。 lowbit(6) 2: 6 110₂, -6 ...1010₂, 110 010 010 2 lowbit(4) 4: 4 100₂, -4 ...1100₂, 100 100 100 4 return x -x def add(self, idx: int, delta: int): 单点更新在位置 idx 增加 delta 更新所有覆盖 idx 的 BIT 节点。 为什么不断加 lowbit BIT[idx] 同时被 BIT[idx lowbit(idx)] 覆盖 BIT[idx lowbit(idx)] 又进一步被更上级覆盖。 这个链就是更新路径。 时间复杂度O(log n) while idx self.n: self.tree[idx] delta idx self.lowbit(idx) def prefix_sum(self, idx: int) - int: 前缀和a[1] a[2] ... a[idx] 为什么不断减 lowbit BIT[idx] 覆盖 [idx - lowbit(idx) 1, idx] 区间。 sum(idx) BIT[idx] sum(idx - lowbit(idx)) 时间复杂度O(log n) result 0 while idx 0: result self.tree[idx] idx - self.lowbit(idx) return result def range_sum(self, left: int, right: int) - int: 区间和a[left] ... a[right] 利用前缀和相减sum(right) - sum(left - 1) return self.prefix_sum(right) - self.prefix_sum(left - 1) # 应用 1逆序对计数 def count_inversions(arr: List[int]) - int: 用树状数组统计逆序对 时间复杂度O(n log n) 空间复杂度O(n) —— 需要离散化 为什么适合用树状数组 从左到右遍历每个元素查询已出现的比它大的元素数 这个查询本质上是区间和BIT 可以 O(log n) 完成。 # 离散化将元素值映射到 [1, n] 范围 # 为什么需要离散化BIT 的索引需要是连续的 # 而原数组的值范围可能很大 sorted_unique sorted(set(arr)) rank {val: i 1 for i, val in enumerate(sorted_unique)} n len(sorted_unique) bit FenwickTree(n) inversions 0 # 从右到左遍历统计比当前元素小的已遍历元素数 # 另一种等价写法从左到右统计已遍历的比当前元素大的 for val in reversed(arr): r rank[val] # 查询 [1, r-1] 的和比 val 小的元素数 inversions bit.prefix_sum(r - 1) # 将当前元素加入 BIT bit.add(r, 1) return inversions # 应用 2利用 BIT 实现动态第 k 小查询 class FenwickTreeWithKth(FenwickTree): 支持查询第 k 小元素的树状数组 场景动态维护有序序列支持插入、删除和查询中位数 def kth(self, k: int) - int: 查询第 k 小的元素k 从 1 开始 为什么可以用倍增法 BIT 天然支持前缀和查询。 通过二分 BInary lifting 技术 可以 O(log n) 找到第 k 个 1 的位置。 idx 0 # 找到最大的 2 的幂次≤ n bit_mask 1 (self.n.bit_length() - 1) while bit_mask 0: next_idx idx bit_mask if next_idx self.n and self.tree[next_idx] k: # 跳过这块区间 k - self.tree[next_idx] idx next_idx bit_mask 1 # idx 指向第 k 个元素的前一个位置 return idx 1 # 测试 if __name__ __main__: # 基本测试 arr [3, 1, 4, 1, 5, 9, 2, 6] bit FenwickTree(len(arr)) for i, val in enumerate(arr, 1): bit.add(i, val) print(f原数组: {arr}) print(f[1,3] 区间和: {bit.range_sum(1, 3)}) # 314 8 print(f[4,6] 区间和: {bit.range_sum(4, 6)}) # 159 15 # 逆序对测试 test_arr [5, 2, 6, 1] print(f\n数组 {test_arr} 的逆序对数: {count_inversions(test_arr)}) # (5,2), (5,1), (2,1), (6,1) 4四、树状数组 vs 线段树的选型边界选择树状数组的场景只需要单点更新 前缀和/区间和查询代码行数有严格限制BIT 的实现通常不到 20 行内存有压力BIT 的空间是 O(n)线段树是 O(4n)必须选线段树的场景需要区间更新 区间查询BIT 可以通过差分做但代码变复杂需要维护区间最值BIT 不支持求最值因为减 lowbit 会丢失信息需要多种操作的组合如区间加 区间求和 区间最大常数因子的差异。BIT 在相同复杂度下的常数因子远小于线段树。BIT 的更新和查询都是简单的 while 循环和位运算而线段树需要递归或手动维护栈。在 10^6 级别的数据上这个差异可能是十几毫秒和几百毫秒的区别。五、总结lowbit 不是魔法它是二进制补码和进位规则的直接推论。理解了x -x为什么恰好等于最低位 1 的值树状数组的整个索引体系就自然揭示了BIT[i] 覆盖 [i-lowbit(i)1, i]前缀和就是不断减 lowbit更新就是不断加 lowbit。树状数组是精巧的工程实现的典范。它只用了数组和位运算就实现了 O(log n) 的前缀和与更新操作。它的简洁背后是对二进制规律的深刻理解——理解了这个规律你不仅能写出树状数组还能在面试中解释它为什么正确。
