树状数组的索引设计：lowbit 不是魔法，是二进制规律的直接推论

树状数组的索引设计：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。加 1：0100。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) = 2），BIT[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 → 6；6 → lowbit(6)=2 → 4；4 → lowbit(4)=4 → 0。每次减掉 lowest bit 1，最多 O(log n) 步。

单点更新：不断加 lowbit。更新 a[3] 需要更新 BIT[3]、BIT[4]、BIT[8]... 因为 lowbit(3)=1 → 3+1=4，lowbit(4)=4 → 4+4=8。每一步都将最低位 1 进位到更高位。

三、树状数组的完整实现与使用场景

""" 树状数组（Fenwick Tree）——完整实现 功能：单点更新 + 区间查询 应用场景：逆序对计数、动态维护前缀和、离线二维偏序 """ from typing import List class FenwickTree: """ 树状数组 所有索引从 1 开始（内部自动处理） 为什么索引从 1 开始：lowbit(0) = 0，会导致死循环。 """ def __init__(self, n: int): """ n: 数组长度 为什么数组大小是 n+1：索引 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 与 ~x+1 的按位与 恰好等于 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)}") # 3+1+4 = 8 print(f"[4,6] 区间和: {bit.range_sum(4, 6)}") # 1+5+9 = 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) 的前缀和与更新操作。它的简洁背后是对二进制规律的深刻理解——理解了这个规律，你不仅能写出树状数组，还能在面试中解释它为什么正确。