当我们学习树状数组（Binary Indexed Tree，也称 Fenwick Tree）时，大多数教程都会告诉我们：

  • 树状数组是一种”树形结构”
  • 通过 i += lowbit(i) 可以”向上找父节点”
  • 通过 i -= lowbit(i) 可以”向下找子节点”
  • 每个节点管理一个特定长度的区间

这些解释看起来合理，但却没有回答一个核心问题：为什么只能跳到这些特定的节点？为什么不是其他的跳跃方式？

更深入地思考，既然树状数组的核心操作都是基于 lowbit(x) = x \& (-x) 这个位运算，那我们是否应该从位运算的角度来理解它的本质？

lowbit 的位运算含义

lowbit(x) 表示 x 的二进制表示中最右边的 1 及其右边所有 0 组成的数值。

lowbit(x) = x \& (-x) — 它提取出 x 二进制表示中最低位的 1 对应的 2 的幂次。

例子：

x二进制lowbit(x)
121100₂4
60110₂2
81000₂8
50101₂1

为什么 x \& (-x) 能得到 lowbit？补码运算中，从右往左找到第一个 1，这个 1 及其右边的 0 在取反加 1 后保持不变，而左边的位全部被翻转。因此 x \& (-x) 只保留了最右边的 1。

tree[i] 的含义

tree[i] 管理从位置 i - lowbit(i) + 1 到位置 i 的区间和。

i区间lowbit
1[1,1]1
2[1,2]2
3[3,3]1
4[1,4]4
5[5,5]1
6[5,6]2
7[7,7]1
8[1,8]8

Query 操作的区间分解

func (bit *BIT) Query(i int) int {
    sum := 0
    for i > 0 {
        sum += bit.tree[i]
        i -= lowbit(i)
    }
    return sum
}

Query(6) 分解：[1,6] = [5,6] ∪ [1,4] → sum = tree[6] + tree[4]

Query(7) 分解：[1,7] = [7,7] ∪ [5,6] ∪ [1,4] → sum = tree[7] + tree[6] + tree[4]

核心理论：贡献关系的位运算刻画

核心问题：当更新位置 b 时，哪些 tree[a] 需要被更新？等价地，b 属于哪些 tree[a] 的管理范围？

根据 tree[a] 的定义，b ∈ tree[a] 的管理范围当且仅当 b ∈ [a - lowbit(a) + 1, a]，即：

b≤a且a−b<lowbit(a)b \le a \quad \text{且} \quad a - b < \text{lowbit}(a)

这个简洁的代数刻画等价于一个纯位运算的刻画。设 a 的二进制表示形如 ...X 1 0...0，其中末尾 k 个 0、lowbit(a) = 2^k、X 是 lowbit(a) 位以上的所有位。则 b ∈ tree[a] 的管理范围当且仅当：

  1. 高位相同：b 在 lowbit(a) 位以上的位与 a 完全相同（都是 X）
  2. 低位有界：b 在 lowbit(a) 位及以下（共 k+1 位）的值落在 [1, lowbit(a)] 区间内

直观理解：管理范围 [a - lowbit(a) + 1, a] 的下端 a - lowbit(a) + 1 = ...X 0 1...1（高位 X、bit k 为 0、bit k-1 到 bit 0 全为 1），上端 a = ...X 1 0...0（高位 X、bit k 为 1、bit k-1 到 bit 0 全为 0）。区间内的所有数高位都是 X，低 k+1 位的值恰好遍历 [1, 2^k] = [1, \text{lowbit}(a)]。

具体验证：a = 6 = 0110₂，lowbit(a) = 2 = 010₂，k = 1，X = 01（bit 2 及以上）。管理范围 [5, 6]：

  • b = 5 = 0101₂：高位 01 与 a 相同；低 2 位 01₂ = 1 ∈ [1, 2] ✓
  • b = 6 = 0110₂：高位 01 与 a 相同；低 2 位 10₂ = 2 ∈ [1, 2] ✓

从 b 构造贡献目标 a

逆向构造：给定 b，找到所有满足上述条件的 a。

观察一个关键性质：若 b ∈ tree[a] 的管理范围（且 b ≠ a），则 b 在 lowbit(a) 对应的位上必为 0。

证明：管理范围内 b ≤ a，且 b 与 a 高位（lowbit(a) 位以上）相同。若 b 在 lowbit(a) 位上也是 1，则 b 在该位及以上与 a 完全一致；又因为 a 在 lowbit(a) 位以下全为 0，要让 b ≤ a，b 在 lowbit(a) 位以下也必须全为 0，此时 b = a，与假设 b ≠ a 矛盾。

这给出了构造算法：贡献目标集合包括 b 本身（平凡情形 a = b），以及——设 lowbit(b) = 2^s，从 bit s+1 开始向左扫描 b 的每个 0 位，每个 0 位都对应一个候选的 lowbit(a) 位置，由此唯一确定一个 a：把该 0 位置 1，并清零所有更低位。

例子 b = 3 = 0011₂，lowbit(b) = 2^0，扫描 bit 1 及更高位（含 bit 1）：

  • bit 1 是 1（跳过）
  • bit 2 是 0 → a = 0100₂ = 4
  • bit 3 是 0 → a = 1000₂ = 8
  • bit 4 是 0 → a = 10000₂ = 16
  • 加上 a = b = 3，贡献目标集合为 {3, 4, 8, 16, ...}

例子 b = 6 = 0110₂，lowbit(b) = 2^1，扫描 bit 2 及更高位（含 bit 2）：

  • bit 2 是 1（跳过）
  • bit 3 是 0 → a = 1000₂ = 8
  • bit 4 是 0 → a = 10000₂ = 16
  • 加上 a = b = 6，贡献目标集合为 {6, 8, 16, ...}

充分性与必要性

充分性：构造算法产出的每个 a 都满足贡献条件。

设构造时选定 b 的某个 0 位为 bit j，并且 bit j 在 lowbit(b) 之上（即 2^j > \text{lowbit}(b)）。构造结果 a 在 bit j 处为 1、bit j-1 到 bit 0 全为 0、bit j 以上与 b 相同。因此 lowbit(a) = 2^j，且：

  • 高位相同：a 在 bit j 以上的位与 b 完全一致 ✓
  • 低位有界：b 在低 j+1 位的值由 bit j（为 0）和 bit j-1 到 bit 0（任意）组成，所以 b 在低 j+1 位的值 ∈ [0, 2^j - 1]。又因为 lowbit(b) < 2^j，b 的最低位 1 出现在 bit 0 到 bit j-1 之间，所以低 j+1 位至少有一个 1，即值 ∈ [1, 2^j - 1] ⊂ [1, \text{lowbit}(a)] ✓

必要性：每个满足贡献条件的 a，都出现在从 b 出发的构造路径上。

b = a 时，a 是路径起点，平凡成立。下设 b ≠ a，且 lowbit(a) = 2^k。由上一节关键性质，b 在 bit k 上是 0。由高位相同条件，a 和 b 在 bit k 以上的位相同。又由低位有界条件，b 在低 k+1 位的值 ∈ [1, 2^k]；既然 bit k 为 0，该值实际 ∈ [1, 2^k - 1]，因此 b 在 bit 0 到 bit k-1 至少有一个 1，即 lowbit(b) < 2^k = lowbit(a)。这说明 bit k 恰好是构造算法允许的 0 位（在 lowbit(b) 之上）；以 bit k 为 lowbit(a) 的位置进行一次构造，得到的正是 a。因此所有合法的 a 都在构造路径上。

充分性 + 必要性表明：构造路径精确等于贡献目标集合。

Update 操作的位运算本质

func (bit *BIT) Update(i, delta int) {
    for i <= bit.n {
        bit.tree[i] += delta
        i += lowbit(i)
    }
}

剩下要论证：i += lowbit(i) 从 b 出发逐步迭代，恰好枚举上一节构造算法允许的所有 a。

设当前迭代值 i = ...Y c 1 0...0，其中末尾 m 个 0（lowbit(i) = 2^m）、bit m 为 1、bit m+1 为 c、bit m+1 以上为 Y。考虑 i + \text{lowbit}(i) = i + 2^m：

  • 若 c = 0：结果为 ...Y 1 0 0...0（bit m+1 变 1、bit m 变 0、bit m-1 到 bit 0 仍为 0）。这恰好是”以 bit m+1 为新的 lowbit、bit m+1 以上保留 Y、bit m+1 以下清零”——等价于从 b 直接选 bit m+1 作为 lowbit(a) 的构造结果。
  • 若 c = 1：发生链式进位，结果为 ...Y' 0...0，其中 bit m+1 链式进位直到遇到更高的 0 位 bit j，bit j 变 1、bit j-1 到 bit 0 全变 0。这等价于从 b 直接选 bit j 作为 lowbit(a) 的构造结果。

无论哪种情况，i += lowbit(i) 一步迭代正好对应”选当前 i 中 lowbit(i) 之上最低的 0 位、置 1、清零更低位”。注意每次跳跃只修改 lowbit(i) 及以上的位，且 lowbit(i) 严格单调递增。归纳可证一个关键不变量：路径上每个 i 在其 lowbit(i) 之上的位与原 b 在那些位上相同（起点 i = b 平凡成立；每次跳跃使 lowbit(i) 上移，新的 lowbit(i) 之上的位等于上一步状态在同一区域的位，归纳保持）。

因此路径上每个 i 都符合构造算法对 a 的要求；反之，构造算法产出的每个 a（按 lowbit(a) 递增排序）也恰好被路径访问到。综合前文充分性与必要性，得证：i += lowbit(i) 从 b 出发的迭代路径精确等于 b 的全部贡献目标。

验证 b = 3：3(0011) + 1(0001) = 4(0100) ✓

验证 b = 6：6(0110) + 2(0010) = 8(1000) ✓

Go 验证程序

下面的程序用真实区间定义的暴力枚举与 i += lowbit(i) 路径进行对比：

package main

import (
	"fmt"
	"sort"
)

func lowbit(x int) int {
	return x & (-x)
}

// 暴力法：用真实定义 b ∈ [a-lowbit(a)+1, a] 枚举所有合法的 a
func bruteForceContributions(b, n int) []int {
	var result []int
	for a := 1; a <= n; a++ {
		if b >= a-lowbit(a)+1 && b <= a {
			result = append(result, a)
		}
	}
	sort.Ints(result)
	return result
}

// 理论法：从 b 出发沿 i += lowbit(i) 枚举
func theoreticalContributions(b, n int) []int {
	var result []int
	for i := b; i <= n; {
		result = append(result, i)
		i += lowbit(i)
	}
	return result
}

func main() {
	n := 16
	allMatch := true
	for b := 1; b <= n; b++ {
		bf := bruteForceContributions(b, n)
		th := theoreticalContributions(b, n)
		match := fmt.Sprintf("%v", bf) == fmt.Sprintf("%v", th)
		if !match {
			allMatch = false
		}
		fmt.Printf("b=%2d (binary=%05b) brute=%v theory=%v match=%v\n",
			b, b, bf, th, match)
	}
	if allMatch {
		fmt.Println("All match.")
	}
}

运行结果对 n = 16 范围内所有 b 验证通过：暴力法（基于区间定义）与理论法（基于 i += lowbit(i)）给出完全相同的贡献集合。这与前文充分性 + 必要性的证明一致。

本文从 CSDN 迁移并重写，原文链接。