企业官网建设流程全解析

第一次接触树状数组（Binary Indexed Tree，也叫 Fenwick Tree）时，很多人都会经历一个很典型的阶段：模板能背下来，题目也能 AC，但心里总觉得有个地方没通。

背下来的代码大概是这个样子的：

int lowbit(int x) { return x & (-x); } void add(int i, int v) { for (; i <= n; i += lowbit(i)) { tree[i] += v; } } int prefixSum(int i) { int res = 0; for (; i > 0; i -= lowbit(i)) { res += tree[i]; } return res; }

写更新时，i不断增大，所以叫“向上”；写查询时，i不断减小，所以叫“向下”。很多人会卡在这里：为什么一个是加 lowbit，一个是减 lowbit？这个看起来不对称的设计，为什么能保证两端都是 O(log n)？

如果只是应付比赛或考试，背模板确实够用。但一旦遇到区间修改、树状数组二分、逆序对、离散化这些变体，或者调试时发现答案总是差一点，你会发现背诵不能解决结构性问题。这篇文章就把“为什么”这一层拆开讲清楚，重点解决两个问题：更新为什么向上，查询为什么向下，以及它们的复杂度为什么都是 O(log n)。

1. 先纠正一个常见的理解误区：这棵树不是一棵“真树”

树状数组名字里带“树”，但它和线段树、平衡树那类带指针、带左孩子右孩子的树并不一样。它没有真正的节点对象，没有递归建树，也没有孩子指针。整个结构就是一块普普通通的一维数组tree。

那“树”在哪里？

在索引之间的跳跃关系上。tree[i]虽然不知道自己的“孩子”是谁，但它知道自己在索引上覆盖哪一段区间。这个区间完全由i的 lowbit 决定：

tree[i]存储的是闭区间[i - lowbit(i) + 1, i]上的聚合值。

这是理解整个树状数组最关键的一句话。下面用n = 16的几个索引来验证：

1.1 为什么恰好覆盖这么一段

观察二进制规律，你会发现 lowbit 的本质是去掉二进制编号最右侧的 1 后面的所有 0，也就是取出最右侧那个 1 所代表的权值。

• 6 = 110，最右侧 1 的权值是10，也就是 2，所以lowbit(6) = 2。
• 12 = 1100，最右侧 1 的权值是100，也就是 4，所以lowbit(12) = 4。
• 8 = 1000，最右侧 1 的权值就是1000，也就是 8，所以lowbit(8) = 8。

一个很容易记住的结论是：

如果lowbit(i) = k，那么tree[i]就负责[i - k + 1, i]这一段。

也就是说，tree[i]的职责范围长度，恰好等于lowbit(i)。

很多初学者拿到树状数组结构图时，会直接用线段树那套理解方式去解读：叶子节点存原数组，内部节点存区间和。但在树状数组里，并没有一棵“显式”的树结构在维护你。你看到的图，其实是低层逻辑关系；到底谁是tree[i]的父节点、谁是它的子节点，完全是由lowbit算出来的。

1.2 为什么不是“完整二叉树”

线段树里每个节点负责的区间是固定的对半拆分，左孩子右孩子也明确；树状数组则完全不同。它负责的区间长度不是靠“均分”来的，而是靠二进制低位拆出来的。

说白了，树状数组是“按二进制权值分块”的数据结构。每个下标 i 能管多长，取决于 i 本身二进制长什么样。这种设计在构建时不需要递归，运行时不传参找儿子，甚至在空间上就是原数组大小 n，而线段树通常要开 4 倍空间。它不是一棵“真树”，却用数组索引之间的位运算，把树形依赖表达得干干净净。

这也是为什么理解 lowbit 比背代码重要：你只有知道tree[i]管的是哪一段，才能理解后面更新和查询为什么是那样跳的。

2. lowbit：为什么它是整个数据结构的算术根基

2.1 一行代码，二进制的分水岭

lowbit 的常见写法是x & (-x)。在大多数编程语言里，负数用的是补码表示。补码的意思是：-x = (~x) + 1。

x & (-x)的效果是保留 x 二进制中最右侧的 1，其余位全部归零。

举几个例子：

x = 12 = 1100 -x = -12 = 0100 （补码形式，只关注取最低位 1 之后的位） lowbit(12) = 0100 = 4 x = 10 = 1010 lowbit(10) = 0010 = 2 x = 7 = 0111 lowbit(7) = 0001 = 1

有的读者可能会疑惑：为什么lowbit(12)不是 8 也不是 2？

因为 12 的二进制是1100，最右侧的 1 在第三位，代表 2³，也就是 4。它左边的 1 更高，右边的位全是 0。所以保留“最低位的 1”这个操作，在二进制世界里就是抠出一个“权值”。

2.2 lowbit 本质上是“最小分块单位”

如果从功能角度看，lowbit 承担了两件事。

第一，它是tree[i]管辖区间长度的度量。tree[i]负责[i - lowbit(i) + 1, i]，而这段长度就是lowbit(i)。

第二，它决定了索引跳跃的步长。更新与查询的两条路径，都是以 lowbit 为台阶往上或往下走。

为什么不选一个固定的块大小，比如 2 或 4？因为固定块大小无法同时满足“查询前缀和”和“单点更新”两个需求。你想要单点更新时快速影响所有相关区域，又想要区间查询时快速合并结果。lowbit 让区间长度与下标二进制绑定，这样每个索引都能高效跳出二进制的 1 位链。

打个比方：lowbit 像是给你一套按 1、2、4、8、16 划分大小的拼图。每次合并或拆散，只需要处理这些“标准件”。标准件数量不超过 2 的幂次，所以单次查询或更新的跳跃次数自然就被压在了二进制位数级别。

3. 更新向上走：i += lowbit(i) 到底在维护什么

现在进入核心问题：为什么更新时，i要加 lowbit。

假设原数组是a[1..n]，要做单点更新：a[3] += v。

a[3]在哪些tree节点里出现过？根据tree[j]覆盖区间[j - lowbit(j) + 1, j]，我们只需要找到所有覆盖位置 3 的 j。

手动枚举几个：

• j = 3：覆盖[3, 3]，包含 3。
• j = 4：覆盖[1, 4]，包含 3。
• j = 8：覆盖[1, 8]，包含 3。
• j = 16：覆盖[1, 16]，包含 3。

你会发现这一串是：3 → 4 → 8 → 16。

而从 3 开始加 lowbit：

• i = 3，lowbit(3) = 1，加完得 4。
• i = 4，lowbit(4) = 4，加完得 8。
• i = 8，lowbit(8) = 8，加完得 16。

恰好就是那条路径。

3.1 为什么祖先一定是“加 lowbit”而不是别的

因为tree[j]覆盖区间的右端点是j，左端点是j - lowbit(j) + 1。如果区间覆盖了一个点i，那么这个区间的右端点j必须满足：

j - lowbit(j) + 1 <= i <= j

你可以验证：所有满足这个条件的j，都会在i不断执行j = i + lowbit(i)的过程中出现。也就是说，覆盖i的所有tree节点，会顺着“从当前位置向右上方跳”的链路一个个被找到。

从二进制角度看也直观：

• 3 = 011，它的 lowbit 是001，加完跳成4 = 100。
• 4 = 100，它的 lowbit 是100，加完跳成8 = 1000。
• 8 = 1000，lowbit 是1000，加完跳成16 = 10000。

每次更新都会把最低位的 1 往更高位推进。

3.2 这棵树上的“父节点”为什么不走右孩子

很多学线段树的人会习惯性想：更新的阶段，应该先更新自己，再更新父节点、祖父节点。树状数组也是这个逻辑，只不过它的父节点不是通过i / 2找到的，而是通过i + lowbit(i)找到的。

那为什么不是i << 1或i + 1这种简单关系？

原因很简单：树状数组的父节点，必须负责一个更大的、且包含当前区间的二进制分块区间。这个分块区间的大小和位置，由父节点二进制的最低位 1 决定。按位运算保证了这种“包含又错开”的结构稳定成立。

3.3 更新复杂度为什么是 O(log n)

从i出发，每次i += lowbit(i)之后，i的二进制最低位 1 的位置至少左移一位。

比如：

• 3 的 lowbit 是 1，加完变成 4，最低位 1 从第 0 位跳到第 2 位。
• 4 的 lowbit 是 4，加完变成 8，最低位 1 从第 2 位跳到第 3 位。
• 8 的 lowbit 是 8，加完变成 16，最低位 1 从第 3 位跳到第 4 位。

对于n以内的数字，二进制位数最多是⌊log₂ n⌋ + 1。既然最低位 1 的位置只会不断提高，那它最多提高⌊log₂ n⌋次就会被推出n的范围。

所以更新的循环次数是 O(log n)。

这里要注意，复杂度上限是“二进制位数级别”，而不是“数字大小级别”。一个 10 万以内的数字，二进制位只有 17 位左右，所以循环次数最多十几二十次。这也解释了为什么树状数组在n = 1e5、1e6量级时跑得飞快。

4. 查询向下走：i -= lowbit(i) 是如何拼出前缀和的

更新是往右上方跳，查询却是往左下方跳。先看一个具体例子。

求前 13 项前缀和prefixSum(13)。

从i = 13开始：

• i = 13：lowbit(13) = 1，累加tree[13]，它覆盖[13, 13]。
• i = 13 - 1 = 12：lowbit(12) = 4，累加tree[12]，它覆盖[9, 12]。
• i = 12 - 4 = 8：lowbit(8) = 8，累加tree[8]，它覆盖[1, 8]。
• i = 8 - 8 = 0，循环结束。

拼起来是：

[1, 13] = [1, 8] ∪ [9, 12] ∪ [13, 13]

完美覆盖，既不重叠，也不遗漏。

如果用区间求和sum(l, r)，就变成prefixSum(r) - prefixSum(l - 1)。这也是为什么树状数组只能做前缀和查询；区间和只是两个前缀和相减。

4.1 为什么拆出来的区间一定是“二进制块”

从二进制看 13：

13 = 1101

查询时，每一步都减去当前数字最低位的 1：

1101 -> 1000 （减去 0101? 不对，稍微换个角度更清楚）

更准确的表达是：

13 = 1101 第一步：最低位 1 的权值是 1，所以取 [13, 13] 剩下：1100 = 12 第二步：12 的最低 1 权值是 4，所以取 [9, 12] 剩下：1000 = 8 第三步：8 的最低 1 权值是 8，所以取 [1, 8] 剩下：0

所以前缀和查询的本质，是把一个前缀区间拆成若干个“长度为 2 的幂”的区间拼接起来。二进制中有多少个 1，就会拆出多少个块。而二进制中 1 的个数不会超过⌊log₂ n⌋ + 1。

4.2 为什么查询是“向下”而不是“向上”

因为我们要的是从 1 到 i 的前缀和，而不是单点 i 所在的所有覆盖区间。

更新是为了告诉所有覆盖当前点的节点“这个点的值变了”，所以必须一路向上找父节点，父节点才会同步。

查询是为了把[1, i]拆成已知的、不重叠的tree节点，所以必须一路向下释放已经算好的小区间。每次减掉 lowbit，其实是把当前区间中最右侧的那一块交给答案。

把这两个逻辑放在一起看，你会得到一条清晰主线：

• 更新时，你要修改的是“影响我的节点”。
• 查询时，你要加起来的是“组成我的片段”。

“影响我的节点”在结构图中位于当前节点上方，所以向上； “组成我的片段”在当前节点左侧或把自己本身拆出去，所以向下。它们不是同一个方向，也不应该相同。

4.3 查询复杂度为什么是 O(log n)

查询过程中，每做一次i -= lowbit(i)，二进制里至少会有一个 1 变成 0。

i = 13的二进制是1101，经历了三步：

1101 1100 1000 0000

三次都是把最低位的 1 消掉。任意一个不超过 n 的数字，二进制中最多有⌊log₂ n⌋ + 1个 1。所以循环次数最多是“二进制中 1 的个数”，必然也是 O(log n)。

值得注意的是，查询的实际速度还取决于 i 的二进制中 1 的密集程度。比如 i=7 二进制是 111，查询就要循环 3 次；i=8 二进制是 1000，查询只要循环 1 次。这比复杂度上限还快，很多情况下平均表现比线段树更轻量。

5. 复杂度证明：为什么两端都是 O(log n)

这一段专门做一个更形式化的总结，因为初学者最容易卡在这里：更新和查询的方向不同，凭什么恰好都是 O(log n)？

5.1 更新：最低位 1 的位置严格递增

设当前数字为 i，二进制表示为...???100...0，其中最低位 1 后面有 k 个 0。

那么：

lowbit(i) = 2^k i + lowbit(i) = ...???100...0 + 100...0

低 k 位变成 0，第 k 位原本的 1 会参与进位，结果至少会影响到第 k 位或更高位。进位的效果是让“最低位 1”的位置移动到更高位置。

因为 i 始终不超过 n，而 n 的二进制位只有⌊log₂ n⌋ + 1位，所以“最低位 1 的位置”最多只能上升这么多次。

这就是更新循环次数 O(log n) 的严格理由。

5.2 查询：二进制 1 的总数严格递减

设当前数字为 i，最低位 1 的权值为 lowbit(i)。

执行后：

i' = i - lowbit(i)

因为最低位 1 变 0，而它右侧本来就全是 0，所以这一次减法至少让二进制中 1 的个数减少 1。

最坏情况下，i 的二进制全是 1，例如：

i = 2^k - 1

它有 k 个 1，因此循环 k 次。k 仍然是⌊log₂ n⌋级别。

这就是查询循环次数 O(log n) 的严格理由。

5.3 为什么树状数组不是 O(1)

有人可能会问：既然每次查询都可能只循环几次，为什么还要说 O(log n) 而不是 O(1)？

因为复杂度描述的是最坏情况。n 很大的时候，比如 n=2³⁰，一个二进制全 1 的数字，查询确实要循环 30 次。但 30 次对一次查询来说非常快，这也是树状数组在工程和竞赛里能大量使用的原因之一。

还有一个容易忽略的点：树状数组的单次操作循环次数不是由 n 的线性规模决定，而是由 n 的二进制长度决定。n = 1e6和n = 1e9在二进制长度上只差 10 位左右，所以它的扩展性比普通数组维护方法好很多。

5.4 和线段树对比一下

线段树每次操作的复杂度也是 O(log n)，但它是通过递归二分树高得到的。树状数组则是通过“二进制分块跳链”得到的。

两者复杂度同级，但树状数组更省空间、代码更短、常数更小。代价是它表达能力有限：不适合处理最大值、最小值这类不满足“可减性”的聚合信息。

如果你的问题只是“单点更新 + 区间求和”，树状数组是首选。

6. 从板子到工程：三个最容易踩的坑和一条排查链路

树状数组代码短，但上手并不代表不会错。实际写题或做项目时，下面几个坑出现频率极高。

6.1 下标从 0 开始

树状数组的下标几乎必须从 1 开始。原因很简单：lowbit(0) = 0，如果你在 i=0 时调用更新或查询，i += lowbit(i)会变成i += 0，死循环。

处理办法有两种：

• 读入数据时把索引整体 +1。
• 用idx + 1作为树状数组里的实际位置。

如果不一致，前缀和会整个错位。

6.2 把单点更新当成赋值

add(i, v)的本意是在原数组第 i 个位置加上一个值 v，不是把原数组第 i 个位置改成 v。如果你把一个数改成另一个数，需要先计算差值，再用差值调用 add。

例如把a[i]从旧值 oldV 改成 newV：

int delta = newV - oldV; add(i, delta); oldV = newV;

如果你直接add(i, newV)，那么更新之后的值是原值加 newV，而不是 newV。这种错误在小规模数据上不太容易发现，因为样例经常只有几次更新，不容易累积。

6.3 离散化之后忘记对应关系

树状数组经常和离散化一起出现，尤其是在逆序对问题里。离散化的本质是把值域压缩成 1..m 之间的连续整数，然后把这个整数作为树状数组下标。

这里最容易出现的错误是：

• 离散化结果从 0 开始，忘了 +1。
• 排序后去重，但在查询时仍然用原数组去比较。
• 数值相等但没有正确处理“等于”的情况，导致统计逆序对时多算或少算。

建议是先在一个小例子上手动模拟一遍离散化结果，再写树状数组部分。

6.4 一条顺向排查链路

如果结果不对，不要一上来就打印整棵 tree。按下面顺序排查：

1. 检查下标是否从 1 开始。
2. 检查树状数组初始化：如果初始数组不是全 0，需要逐个 add，而不是直接给 tree 赋值。
3. 手动模拟某次 add：选定一个小索引，比如 i=3，手动算出 3、4、8、16 这条更新链，检查代码是否访问了这些位置。
4. 手动模拟某次查询：选定一个 i，比如 i=13，手动拆出 [13,13]、[9,12]、[1,8]，再用手算前缀和验证。
5. 检查更新次数和数据范围：n 是否超出 tree 数组大小，是否中间结果已经超过 int 范围。

排查时最好先用 n=8 或 n=16 的小数据。小数据能手工列出每个 tree[i] 覆盖区间，也最容易暴露 lowbit 方向写反的问题。

这套排查顺序的核心思路是：先确认数据组织方式，再确认单次操作路径，最后确认整体累加结果。不要一开始就去调整 lowbit 的实现，也不要把所有错误都归因于位数不对。

7. 树状数组的真正价值：不只是前缀和，还可以上溯和二分

如果只是单点加、区间求和，树状数组的定位还比较窄。但当你理解了 lowbit 跳链之后，会发现它能扩展出一系列很自然的变体。

7.1 逆序对：统计逻辑建立在“可加性”上

逆序对问题的经典做法是：

1. 对原数组离散化。
2. 从前往后扫描，每遇到一个数 a[i]，就在树状数组下标为 rank(a[i]) 的位置加 1。
3. 在加之前或之后，用前缀和查询已经出现过的、比当前数大的数字个数。

如果从前往后扫，统计“已出现过且比当前数大”的数量，就是i - 1 - prefixSum(rank)；如果更偏好减掉左侧比当前数小的，可以用prefixSum(n) - prefixSum(rank)。

这背后的逻辑是：树状数组维护的是权值的频次分布。单点更新是更新某个权值的出现次数，前缀查询是统计某个值域范围内的已经出现次数。lowbit 的查询链正好把频次区间拆成连续的不相交块，所以统计复杂度也是 O(log n)。

7.2 树状数组二分：找第 k 小

树状数组一个很有意思的高级用法，是在它上面做二分查找，找“前缀和达到某个阈值的最小下标”。

原理是：

树状数组的 tree[i] 是“按 2 的幂分块”的，所以我们可以从高到低尝试每个二进制位，跳跃式地构造答案。

// 找到最小的 pos，使得 prefixSum(pos) >= k // 需要 tree 中存的值都是非负的 int kth(int k) { int pos = 0; int maxPow = 1; while ((maxPow << 1) <= n) { maxPow <<= 1; } for (int step = maxPow; step > 0; step >>= 1) { int nextPos = pos + step; if (nextPos <= n && tree[nextPos] < k) { k -= tree[nextPos]; pos = nextPos; } } return pos + 1; }

这段代码看起来和普通二分不同，但它本质上是在枚举答案的二进制位。每次尝试加入一个 step 时，tree[pos + step]恰好覆盖了一个连续的块。如果tree[pos + step]小于剩余 k，说明答案在更右边，把 k 减掉这块的值，再继续尝试更小的 step。

这个技巧之所以能成立，正是因为在树状数组里，tree[i]覆盖的区间长度就是lowbit(i)，而枚举 step 的过程中，pos + step的组合可以构造出“从左往右跨过若干个连续块”的效果。

利用这个能力，可以避免在树状数组外面再套一次二分，从而把“单次找第 k 小”从 O(log² n) 降成 O(log n)。

7.3 区间修改 + 区间查询：两个树状数组

常规树状数组是单点更新、前缀查询。要做区间修改和区间查询，可以用差分数组。

设差分数组 d[i] = a[i] - a[i-1]，那么：

• 区间 [l, r] 加 v，变成d[l] += v、d[r+1] -= v。
• 前缀和sum(1..x)可以展开成：

(x + 1) * Σd[i] - Σ(i * d[i])

所以用两个树状数组：

bit1[i] 维护 d[i]; bit2[i] 维护 i * d[i];

区间修改就更新两次，区间查询就用两个前缀和组合：

long long prefixSum(int x) { return (x + 1) * sum(bit1, x) - sum(bit2, x); } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }

这个变体看起来复杂，但核心没有变：更新时仍然一路向上加，查询时仍然一路向下减。lowbit 的跳链机制完全没有改变。

7.4 为什么这些变体都能复用同一套跳链

因为所有变体都建立在同一个前提上：

任意前缀 [1, x] 都可以被若干棵“以 lowbit 划分的区间块”无损拆解。

只要你维护的信息满足“可加性”，并且能通过“一加一减”得到目标区间信息，树状数组这套跳链就适用。它之所以能从小小的前缀和扩展到二维偏序、区间修改、第 k 小问题，正是因为 lowbit 把二进制分块的抽象能力固化了下来。

当然，也要注意边界：

• 如果维护的信息不满足“可减性”，比如最大值、最小值，树状数组很难直接支持区间查询。这时更推荐线段树。
• 如果操作是“区间赋值”而不是“区间加”，并且还要求快速查询，树状数组处理起来很别扭，线段树带 lazy 标记会更自然。
• 如果值域不是 1..n，通常需要离散化，不能直接拿原始大数值当下标。

8. 收束：理解 lowbit，才算是真正拥有树状数组

回到最开始的问题。

更新时向上跳，是因为一个位置的值发生变化，所有覆盖它的上层区间块都要同步更新；查询时向下跳，是因为一个前缀和要拆成若干个二进制分块，才能不重不漏地加出答案。

两条路径方向相反，但都基于同一个 lowbit。更新跳的是“父链”，查询消的是“分块链”。前者受位数的限制，后者受二进制中 1 的个数限制。无论从哪一端看，都落在 O(log n) 上。

这其实是一个值得记住的思维框架：

1. 遇到树状数组，先问：tree[i]管的是哪段区间？
2. 再问：更新一个点，哪些 tree 节点要变？答：沿i += lowbit(i)向上。
3. 最后问：查询一个前缀，我要拆哪些块？答：沿i -= lowbit(i)向下。

如果哪天你忘了树状数组代码，只需要花十秒钟推一下tree[i]的覆盖范围和 lowbit 公式，模板就能自己重新长出来。

真正有价值的东西，从来不是那几行代码，而是代码背后那条由二进制位控制的跳链。理解它之后，树状数组就不再是一个要背的模板，而是一个可以信任、可以扩展、可以自己调试的数据结构基础。