企业官网建设流程全解析

这次我们来看一个出现频率很高、但细节容易讲混的数据结构：树状数组（Binary Indexed Tree，BIT / Fenwick Tree）。

它经常和线段树放在一起比较，但代码比线段树短得多，核心就是两个while循环。然而恰恰是这两个循环的方向，让很多人背了模板也说不清楚：为什么更新要向上走，查询要向下走？lowbit(x) = x & -x到底取了什么？两个循环都号称O(log n)，这个复杂度从哪来？

这篇文章不铺垫背景，直接围绕“区间覆盖表”展开。我会先告诉你tree[i]到底存了什么，再解释lowbit的位运算原理，接着分别推导“查询向下”和“更新向上”，最后证明O(log n)的来源。附带三样可以直接用的东西：完整代码模板、逆序对实战、树状数组上二分。

适合两类读者：刚学树状数组、想彻底理解原理的初学者；以及背过模板、但面试或写题时被问到底层逻辑会卡住的进阶选手。

1. 核心能力速览

记住一句话：更新向上，查询向下，lowbit决定每一步走多远。

2. 先拆本质：tree[i] 到底存了哪个区间

树状数组看似是一棵隐式二叉树，实际上它没有左孩子右孩子，只有一个额外的规则：

tree[i]存储的是原数组从i - lowbit(i) + 1到i这段区间的和。

用公式写就是：

tree[i] = a[i - lowbit(i) + 1] + a[i - lowbit(i) + 2] + ... + a[i]

也就是说，tree[i]覆盖的区间长度正好是lowbit(i)。

以n = 8为例，展开看：

这张表就是整个树状数组的“地图”。

tree[4]不是只存a[4]，它存的是a[1] + a[2] + a[3] + a[4]。tree[6]不是只存a[6]，它存的是a[5] + a[6]。很多初学误区来自这里：误以为tree[i]只和a[i]有关，实际上它是一段区间和。

为什么要这样划分？因为任意一个前缀[1, x]可以被拆成若干个“刚好按lowbit切割”的不相交区间，并且这些区间分别对应某个tree节点。

例如查询[1, 7]的和：

• lowbit(7) = 1，取tree[7]，覆盖[7, 7]；
• 7 - 1 = 6，lowbit(6) = 2，取tree[6]，覆盖[5, 6]；
• 6 - 2 = 4，lowbit(4) = 4，取tree[4]，覆盖[1, 4]；
• 4 - 4 = 0，结束。

所以：

sum(7) = tree[7] + tree[6] + tree[4] = a[7] + (a[5] + a[6]) + (a[1] + a[2] + a[3] + a[4])

覆盖恰好完整，不重不漏。这就是“查询向下”的直觉来源：从x开始，每次减去lowbit(x)，相当于把一个大前缀切成一串右端点递减的区间块。

3. lowbit：树状数组的步长怎么算

lowbit(x)的官方定义是：x的二进制表示中，最低位1所代表的数值。

举例：

• x = 6，二进制是110，最低位1在第 2 位，所以lowbit(6) = 2；
• x = 5，二进制是101，最低位1在第 1 位，所以lowbit(5) = 1；
• x = 8，二进制是1000，最低位1在第 4 位，所以lowbit(8) = 8。

列出1到8的lowbit：

为什么x & (-x)能取到最低位1？

因为在补码表示下，-x等价于~x + 1。~x会把x的所有位取反，+1之后，只有x从低位开始第一个1及其右侧的0会被保留为“不变”，更高位全部取反。x和-x按位与之后，高于最低位1的部分全部变成0，低于最低位1的部分本来就是0，所以结果正好是那个最低位1代表的十进制数。

代码写成函数：

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

Python 也一样：

def lowbit(x): return x & -x

这里有个常见错误：不要把lowbit写成x & (x - 1)。x & (x - 1)的作用是“把最低位 1 抹成 0”，结果是x - lowbit(x)，不是lowbit(x)。方向反了，树状数组的两个循环就会全部乱掉。

4. 查询向下：前缀和为什么要一路向左减

先看查询代码：

int sum(int x) { int res = 0; while (x > 0) { res += tree[x]; x -= lowbit(x); } return res; }

每一步都在执行：

x -> x - lowbit(x)

这个方向是“向左下方走”。为什么不能是x + lowbit(x)？因为查询的目标是前缀和[1, x]，我们需要把[1, x]拆成若干小区间，而不是去覆盖更大的区间。每次减去lowbit(x)，实际上是在把“当前这块区间”从大前缀里切出去。

手动走一遍sum(6)：

• x = 6，lowbit(6) = 2，取tree[6]；
• x = 6 - 2 = 4，lowbit(4) = 4，取tree[4]；
• x = 4 - 4 = 0，结束。

结果：

sum(6) = tree[6] + tree[4] = (a[5] + a[6]) + (a[1] + a[2] + a[3] + a[4])

恰好是前 6 个元素的和。

再看sum(7)：

7 -> 6 -> 4 -> 0

对应：

sum(7) = tree[7] + tree[6] + tree[4]

从这里能直观感受到：查询向下，本质上是“二进制拆区间”。7的二进制是111，拆成100 + 010 + 001，对应区间长度分别是4 + 2 + 1，刚好是完整的7。

区间查询也很简单：

int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }

用两个前缀和相减，复杂度依然是O(log n)。

5. 更新向上：单点修改为什么要一路向右加

更新代码：

void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += lowbit(idx); } }

每一步执行：

idx -> idx + lowbit(idx)

为什么是加？因为当a[idx]发生变化时，所有“覆盖 idx 这个位置的 tree 节点”都要同步变化。这些节点不只有tree[idx]，还有它的若干父节点。

看一个例子。如果修改a[5]，哪些tree节点包含位置 5？

• tree[5]覆盖[5, 5]，包含位置 5；
• idx = 5 + lowbit(5) = 6，tree[6]覆盖[5, 6]，包含位置 5；
• idx = 6 + lowbit(6) = 8，tree[8]覆盖[1, 8]，包含位置 5；
• idx = 8 + lowbit(8) = 16 > n，结束。

所以更新路径是：

5 -> 6 -> 8

这三个节点必须全部加上同一个delta。

再看修改a[3]：

• 3 -> 4 -> 8

tree[3]覆盖[3, 3]，tree[4]覆盖[1, 4]，tree[8]覆盖[1, 8]，全部包含位置 3。

这里就是“更新向上”的来源。idx += lowbit(idx)不是在寻找内存里相邻的节点，而是在“向上找父区间”。树状数组虽然代码里没有left、right指针，但通过lowbit已经隐式地把所有节点组织成了树形覆盖结构。

6. 为什么都是 O(log n)：二进制位数视角

这是很多人最想搞清楚、但往往被一句“因为有 log 层”带过的问题。树状数组既没有显式的树结构，也没有递归栈，为什么两个循环都是O(log n)？

核心原因不是“层数”，而是“二进制位数”。

对于任意正整数x，如果n <= 2^w - 1，那么x的二进制位数为w，其中：

w = floor(log2(n)) + 1

也就是说，w = O(log n)。

先看查询方向：

x -= lowbit(x)这个操作，等价于把x的二进制表示中最低位的1直接抹掉。

例如x = 7，二进制111，减去lowbit(7)=1后变成110，最低位1被抹掉；x = 6，二进制110，减去lowbit(6)=2后变成100，最低位1被抹掉；x = 4，二进制100，减去lowbit(4)=4后变成0。

所以查询循环真正的执行次数，等于x的二进制中1的个数，也就是popcount(x)。而popcount(x)最大不会超过二进制位数w。

结论：

sum(x) 的循环次数 <= popcount(x) <= w = O(log n)

再看更新方向：

idx += lowbit(idx)和查询不同，不是简单删除一个1。这一步本质上是“二进制进位”。

以idx = 5为例，二进制101：

5 + lowbit(5) = 5 + 1 = 6 => 二进制 110 6 + lowbit(6) = 6 + 2 = 8 => 二进制 1000

每次加lowbit，都会让最低位的1向左移动，或者引发一次进位。整个过程中，参与变化的二进制位不会超过w个，所以最坏情况下循环次数也控制在O(w)，也就是O(log n)。

不需要担心会不会出现每一次只加一点点、导致循环很多次的情况。最典型的是从奇数i = 1开始更新：

1 -> 2 -> 4 -> 8 -> 16 -> ...

即使从i = 1一直跳到超过n，也不过是沿着 2 的幂跳，最多log2(n) + 1次。

所以两个方向的循环本质一致：查询向下是“删低位 1”，更新向上是“低位 1 向左进位”，二者都受二进制位数限制。而二进制位数就是log2(n)级别。

这个结论也解释了为什么树状数组操作是O(log n)，而不是O(n)：数组长度即使到1e5，二进制位数也只有约 17 位；到1e6，也只有约 20 位。循环次数非常有限。

7. 完整代码模板：建树、更新、查询

写一个可以直接用的 C++ 结构体：

#include <bits/stdc++.h> using namespace std; struct Fenwick { int n; vector<long long> tree; Fenwick(int n) : n(n), tree(n + 1, 0) {} void add(int idx, long long delta) { while (idx <= n) { tree[idx] += delta; idx += idx & (-idx); } } long long sum(int idx) { long long res = 0; while (idx > 0) { res += tree[idx]; idx -= idx & (-idx); } return res; } long long rangeSum(int l, int r) { return sum(r) - sum(l - 1); } };

初始化方式有两种：

第一种最直观，对每个元素调一次add：

Fenwick bit(n); for (int i = 1; i <= n; i++) { bit.add(i, a[i]); }

复杂度O(n log n)。

第二种是线性建树，利用父节点累加：

Fenwick bit(n); for (int i = 1; i <= n; i++) { bit.tree[i] += a[i]; int parent = i + (i & (-i)); if (parent <= n) { bit.tree[parent] += bit.tree[i]; } }

原理很简单：bit.tree[i]最终要成为a[i - lowbit(i) + 1 ... i]的和，而它的父节点是i + lowbit(i)。把当前节点加到父节点上，最后父节点自然会包含所有子区间的和。复杂度O(n)。

Python 版本：

class BIT: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def add(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += idx & -idx def sum(self, idx): res = 0 while idx > 0: res += self.tree[idx] idx -= idx & -idx return res def range_sum(self, l, r): return self.sum(r) - self.sum(l - 1)

8. 进阶应用一：树状数组求逆序对

树状数组最经典的进阶应用之一就是逆序对。

问题描述：给定数组a，求有多少对下标(i, j)满足i < j且a[i] > a[j]。

朴素做法是两层循环，复杂度O(n^2)。用树状数组可以做到O(n log n)。

思路：

1. 先对数组元素离散化，把值域映射到1...m；
2. 从左往右遍历原数组；
3. 对当前元素x，已经插入过的元素中，比x大的数量等于：

已插入总数 - 已经插入且 <= x 的数量

4. 累加到答案，然后把x插入树状数组。

C++ 实现：

vector<long long> a; vector<long long> vals = a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); Fenwick bit(vals.size()); long long ans = 0; for (long long x : a) { int idx = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; // 已经插入的元素总数是 bit.sum(m) // 小于等于 x 的数量是 bit.sum(idx) ans += bit.sum(vals.size()) - bit.sum(idx); bit.add(idx, 1); }

注意两个细节：

• 下标从1开始，离散化后idx = lower_bound(...) + 1；
• 逆序对数量最大是n * (n - 1) / 2，记得用long long，不要用int。

如果题目要求的是“严格大于”，我们查询bit.sum(idx)后，用总数减去它即可。如果要求“非严格大于”，也就是a[i] >= a[j]，则需要用bit.sum(idx - 1)。

9. 进阶应用二：树状数组上二分找第 k 小

树状数组不仅可以求前缀和，还能在O(log n)内找到“前缀和第一个大于等于 k 的位置”。这个功能类似有序序列的lower_bound，常用于在线排名系统、动态集合第 k 小。

原理是利用二进制倍增：从最高位 2 的幂开始尝试，如果跳过去之后，tree里累积的和仍然小于k，就跳过去，同时减去这部分和；否则停留在原地。

为什么可以用tree数组直接二分？因为在 BIT 中，tree[i + step]往往维护了一段长度为lowbit(i + step)的区间和，当我们从高到低枚举步长时，可以保证每次跨越的区间都属于同一个层级，不会漏算。

C++ 实现：

int kth(int k) { int idx = 0; int step = 1; while ((step << 1) <= n) { step <<= 1; } for (; step; step >>= 1) { int nxt = idx + step; if (nxt <= n && tree[nxt] < k) { idx = nxt; k -= tree[nxt]; } } return idx + 1; }

这里要求tree存储的是每个位置的出现次数，整体满足前缀和单调不减。如果tree里存的是普通区间和或带有负数，这个方法不成立。

测试思路：假设有m个数，一共插入了total个，那么k的范围是[1, total]。调用kth(k)返回的是“第 k 小的数对应的离散化下标”，再映射回原值即可。

10. 功能测试与效果验证

算法代码最怕“看上去对，手一跑就错”。建议写一个暴力对拍脚本，随机生成数据，把树状数组和朴素数组的结果对照。

Python 示例：

import random class BIT: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def add(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += idx & -idx def sum(self, idx): res = 0 while idx > 0: res += self.tree[idx] idx -= idx & -idx return res bit = BIT(10) arr = [0] * 11 for _ in range(2000): idx = random.randint(1, 10) delta = random.randint(-5, 5) bit.add(idx, delta) arr[idx] += delta for q in range(1, 11): assert bit.sum(q) == sum(arr[1:q + 1]), f"failed at q={q}" print("all tests passed")

如果对拍通过，说明add和sum的核心逻辑没问题。

手动验证时也可以用一组小数据：

• 原数组a = [1, 3, 2]；
• 初始化 BIT；
• sum(2)应该是4；
• add(2, 2)之后a = [1, 5, 2]；
• sum(3)应该是8。

走一遍就知道循环方向对不对。

11. 性能观察与适用边界

树状数组在实际竞赛