企业官网建设流程全解析

之前在刷算法题和准备面试的过程中，树状数组（Binary Indexed Tree）一直是一个“背模板能写，但不深究就讲不清原理”的数据结构。尤其是lowbit、更新向上、查询向下这三句话，很多资料直接抛出来，却不解释为什么要这么做。等你真的去思考i += lowbit(i)和i -= lowbit(i)背后的二进制规律时，才会发现树状数组其实是一个非常精巧的设计。

这篇文章想把树状数组的底层逻辑完整拆开，围绕lowbit这条主线，讲清楚单点更新为什么向上走，前缀查询为什么向下走，以及为什么这两个操作都能稳定在 O(log n)。同时我会结合完整代码示例、运行结果和题目场景（逆序对、树状数组上二分），让新手也能从 0 到 1 掌握这个数据结构。文章中的代码以 C++ 和 Python 为主，核心模板可以直接复制到你的工程或竞赛代码中使用。

1. 背景与核心概念：树状数组到底解决了什么问题

1.1 从一个简单需求说起

假设你现在维护一个长度为 n 的整数数组，需要支持两类操作：

1. 修改某个位置上的元素值。
2. 查询前 i 个元素的和，也就是前缀和。

如果使用普通数组：

如果使用前缀和数组：

可以看到，普通数组和前缀和数组都只能“一边快”。一旦数据规模达到 10^5、10^6，且操作次数很多时，O(n) 的代价就不可接受了。树状数组就是在这个背景下产生的：它用一组树状结构维护区间和，让单点修改和前缀查询的复杂度同时变成 O(log n)。

1.2 树状数组中的几个关键名词

• 原始数组 a[1..n]，下标从 1 开始。
• 树状数组 c[1..n]，c[i] 并不是存储 a[i] 本身，而是存储某个区间[i - lowbit(i) + 1, i]的和。
• lowbit(i)表示 i 的二进制表示中，最低位的 1 及其后面所有 0 组成的数值。

例如：

• lowbit(6) = 2，因为 6 的二进制是 110，最低位 1 在第 1 位（从 0 开始计数），值是 2。
• lowbit(8) = 8，因为 8 的二进制是 1000，最低位 1 在第 3 位，值是 8。
• lowbit(5) = 1，因为 5 的二进制是 101，最低位 1 在第 0 位，值是 1。

1.3 树状数组的适用场景

树状数组最经典的场景包括：

• 单点更新、区间求和（前缀和）。
• 区间更新、单点查询（配合差分技巧）。
• 求逆序对数量。
• 动态维护有序集合中第 k 小元素。
• 二维树状数组处理子矩阵求和问题。

它和线段树相比，优点是代码短、常数小、实现简单；缺点是适用的操作范围相对固定，比如区间最值问题用树状数组就比较麻烦。因此在很多算法竞赛和面试题中，树状数组是优先考虑的“轻量级”数据结构。

2. 环境准备与代码模板：先搭好可运行的框架

2.1 示例环境说明

本文示例以常见环境为例，重点演示代码思路，版本不需要过于纠结：

• C++：需要支持 C++11 及以上标准，推荐使用 g++ 编译。
• Python：需要 Python 3.6 及以上版本。
• 调试方式：本地命令行编译运行，或直接在在线评测平台提交。

C++ 编译命令示例：

g++ -std=c++11 -O2 -o bit bit.cpp ./bit

Python 运行命令示例：

python3 bit.py

2.2 工程文件结构

为了演示方便，建议把封装好的树状数组单独放在一个类或结构体中。示例结构如下：

tree_array_demo/ ├── bit.cpp # C++ 完整示例 ├── bit.py # Python 完整示例 └── README.md # 说明文件

2.3 为什么下标从 1 开始

树状数组的经典实现中，原数组 a 和树状数组 c 都从下标 1 开始使用。这不是为了刁难新手，而是因为lowbit的相关计算在正数下标上更简洁。如果下标从 0 开始，i -= lowbit(i)可能会让索引变成负数，反而增加边界判断。所以本文统一按下标从 1 开始处理。

下面先给出核心模板。C++ 版本：

// 文件路径：bit.cpp #include <bits/stdc++.h> using namespace std; class FenwickTree { private: vector<int> tree; int n; int lowbit(int x) { return x & -x; } public: FenwickTree(int size) : n(size) { tree.resize(n + 1, 0); } // 单点更新：给位置 idx 增加 delta void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += lowbit(idx); } } // 前缀查询：查询 [1, idx] 的和 int query(int idx) { int res = 0; while (idx > 0) { res += tree[idx]; idx -= lowbit(idx); } return res; } }; int main() { vector<int> a = {0, 1, 3, 5, 7, 9, 11}; int n = 6; FenwickTree bit(n); for (int i = 1; i <= n; ++i) { bit.add(i, a[i]); } cout << "sum[1..4] = " << bit.query(4) << endl; cout << "sum[2..6] = " << bit.query(6) - bit.query(1) << endl; return 0; }

预期输出：

sum[1..4] = 16 sum[2..6] = 35

Python 版本：

# 文件路径：bit.py class FenwickTree: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def lowbit(self, x): return x & -x def add(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += self.lowbit(idx) def query(self, idx): res = 0 while idx > 0: res += self.tree[idx] idx -= self.lowbit(idx) return res a = [0, 1, 3, 5, 7, 9, 11] n = 6 bit = FenwickTree(n) for i in range(1, n + 1): bit.add(i, a[i]) print("sum[1..4] =", bit.query(4)) print("sum[2..6] =", bit.query(6) - bit.query(1))

运行结果与 C++ 版本一致。这段模板是整个树状数组的核心，后面所有实战案例都基于它展开。

3. 核心原理拆解：lowbit 到底是什么

3.1 lowbit 的数学定义

lowbit(x)定义为：在整数 x 的二进制表示中，保留最低位的 1，并将其右侧所有位都置 0 后得到的数值。

例如：

从表里能看出一个直观规律：lowbit(x)的结果一定是 2 的幂次，因为它的二进制形式只有一个 1。

3.2 用位运算实现 lowbit

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

这里的关键在于负数的补码表示。在计算机中，-x等于~x + 1，也就是把 x 的每一位取反再加 1。当你对 x 和 -x 做按位与时，x 中比最低位 1 更高的所有位都会和 -x 的对应位相反，结果为 0；而最低位 1 及右侧的 0 会被原样保留。

举个例子，x = 6 时：

x = 000...0110 -x = 111...1010 x & -x = 000...0010 = 2

所以x & -x得到的正是lowbit(x)。这也是树状数组中最核心的一行代码。

3.3 lowbit 在树状数组中的角色

树状数组中，每个节点 c[i] 负责的区间长度恰好是lowbit(i)，区间范围是[i - lowbit(i) + 1, i]。

举例说明：

• c[4] 负责 [4 - 4 + 1, 4] = [1, 4]。
• c[6] 负责 [6 - 2 + 1, 6] = [5, 6]。
• c[7] 负责 [7 - 1 + 1, 7] = [7, 7]。

这种“按二进制最低位 1 决定覆盖范围”的方式，让树状数组的所有操作都可以通过不停移动最低位 1 来完成。只要理解了这个覆盖关系，后续的“更新向上、查询向下”就很容易想通。

4. 单点更新：为什么必须向上走

4.1 更新操作要解决什么问题

当我们修改 a[i] 时，所有维护的区间包含 i 的 c[j] 都需要更新。问题在于，怎么快速找到这些 c[j]？

答案就是反复执行：

j = j + lowbit(j)

从 i 本身开始，每次把最低位的 1 向左移动，直到超过 n。

4.2 一次完整更新过程

假设 n = 8，现在要执行add(3, delta)，也就是给 a[3] 增加 delta。

更新路径如下：

j = 3 lowbit(3) = 1，所以下一个 j = 3 + 1 = 4 lowbit(4) = 4，所以下一个 j = 4 + 4 = 8 lowbit(8) = 8，所以下一个 j = 8 + 8 = 16 16 > n，停止

最终更新的节点是 c[3]、c[4]、c[8]。

为什么是这三个节点？因为：

• c[3] 负责 [3, 3]，显然包含 3。
• c[4] 负责 [1, 4]，包含 3。
• c[8] 负责 [1, 8]，包含 3。

再验证一个例子：add(5, delta)。

j = 5 lowbit(5) = 1，下一个 j = 6 lowbit(6) = 2，下一个 j = 8 8 > n 停止

更新的节点是 c[5]、c[6]、c[8]。检查覆盖区间：

• c[5] 负责 [5, 5]，包含 5。
• c[6] 负责 [5, 6]，包含 5。
• c[8] 负责 [1, 8]，包含 5。

规律成立。

4.3 为什么i += lowbit(i)能找到所有包含 i 的区间

核心秘密在二进制。当执行i += lowbit(i)时，其实是在把 i 二进制中的最低位 1 向更高位进位。

例如：

i = 3 二进制 011 lowbit = 1 二进制 001 3 + 1 = 4 二进制 100 i = 5 二进制 101 lowbit = 1 二进制 001 5 + 1 = 6 二进制 110 lowbit(6) = 2 二进制 010 6 + 2 = 8 二进制 1000

每一次进位，新的 i 的“最低位 1”的位数都会至少提高 1 位。这样的节点数量最多等于二进制位数，也就是 O(log n)。因此单点更新的复杂度是 O(log n)。

4.4 更新方向的记忆技巧

很多初学者会把add写反，写成i -= lowbit(i)。这里给一个记忆方法：单点更新是“向上传递变化”。你修改了叶子节点 a[i] 之后，所有覆盖它的上一层节点都要跟着改。在树状数组的二进制视角里，上一层节点就是通过不断向右上方的进位得到的，所以用+=。

C++ 实现：

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

Python 实现：

def add(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += self.lowbit(idx)

5. 前缀查询：为什么必须向下走

5.1 查询操作要解决什么问题

查询前缀和sum[1..i]时，需要把区间 [1, i] 拆成若干段互不重叠的“树状数组节点”，然后把这些节点的值累加起来。问题是如何高效拆分？

答案就是反复执行：

i = i - lowbit(i)

从 i 本身开始，每次消去最低位的 1，直到 i 变成 0。

5.2 一次完整查询过程

沿用 n = 8 的例子，查询sum[1..7]：

i = 7 lowbit(7) = 1，累加 c[7]，i = 7 - 1 = 6 lowbit(6) = 2，累加 c[6]，i = 6 - 2 = 4 lowbit(4) = 4，累加 c[4]，i = 4 - 4 = 0 停止

最终累加的节点是 c[7]、c[6]、c[4]。

用区间覆盖展开：

c[7] 负责 [7, 7] c[6] 负责 [5, 6] c[4] 负责 [1, 4]

合起来正好是 [1, 7]，没有重叠也没有遗漏。

再验证查询sum[1..6]：

i = 6 累加 c[6]，i = 6 - 2 = 4 累加 c[4]，i = 4 - 4 = 0

c[6] 覆盖 [5, 6]，c[4] 覆盖 [1, 4]，合计 [1, 6]。

5.3 为什么i -= lowbit(i)能拆分区间

从二进制角度看，i -= lowbit(i)相当于把 i 二进制中最右侧的 1 直接改成 0。

例如：

i = 7 二进制 111 i - 1 = 6 二进制 110 （消掉最低位 1） i = 6 二进制 110 i - 2 = 4 二进制 100 （消掉最低位 1） i = 4 二进制 100 i - 4 = 0 二进制 000 （消掉最低位 1）

每次消去一个 1，区间 [1, i] 就被拆掉一块由lowbit(i)长度覆盖的区间。二进制中 1 的个数有限，最多是 O(log n) 个，所以查询复杂度也是 O(log n)。

5.4 查询方向的记忆技巧

查询和更新方向相反，用的是-=。可以这样记：查询前缀和时，你现在所处的位置代表“还剩下 [1, i] 这段没统计完”。你当前节点 c[i] 自己覆盖了最右侧的lowbit(i)个元素，把这些元素加起来之后，剩下的问题变成了查询 [1, i - lowbit(i)]，所以 i 向左下走。

C++ 实现：

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

Python 实现：

def query(self, idx): res = 0 while idx > 0: res += self.tree[idx] idx -= self.lowbit(idx) return res

6. 复杂度分析：O(log n) 到底是怎么来的

6.1 更新操作的操作次数上界

在add过程中，每次i += lowbit(i)会让最低位 1 的位置向左移动。我们可以这样理解：如果 i 的二进制有 k 位，那么最低位 1 最多只能从第 0 位移动到第 k-1 位，进位次数不超过 k。

n 的二进制位数是log2(n) + 1，因此更新的操作次数是 O(log n)。

6.2 查询操作的操作次数上界

在query过程中，每次i -= lowbit(i)会消去二进制中最低位的一个 1。一个数的二进制表示中最多有log2(n) + 1个 1，因此查询的操作次数也是 O(log n)。

6.3 通过一个小实验观察操作次数

可以在代码里加一个计数器，验证add(3, delta)在 n = 100000 时到底执行了几次。

int cnt = 0; int idx = 3; while (idx <= 100000) { idx += idx & -idx; cnt++; } cout << cnt << endl;

输出一次 run 就知道，这个值远小于 100000，通常只有十几到二十几次。这就是 O(log n) 的直观体验。

6.4 建树的 O(n) 方法

如果从空树开始，对每个位置执行add(i, a[i])，建树复杂度是 O(n log n)。对于大多数题目来说已经足够快。但如果 n 特别大，可以用更巧妙的 O(n) 建树方法：

// 先直接把 a[i] 放入 c[i] for (int i = 1; i <= n; ++i) { c[i] += a[i]; } // 向上累加给父节点 for (int i = 1; i <= n; ++i) { int parent = i + (i & -i); if (parent <= n) { c[parent] += c[i]; } }

这个方法的核心是：每个 c[i] 先保存叶子值，然后一层层地向上累加。总操作次数是 n + n/2 + n/4 + ... = O(n)。

7. 完整实战案例：用树状数组求逆序对数量

7.1 题目描述与思路

给定一个数组，求其中逆序对的数量。所谓逆序对，是指满足i < j且a[i] > a[j]的数对。

经典做法很多，比如归并排序。使用树状数组也很方便，步骤是：

1. 对原数组离散化，把数值映射到1..m的排名范围。
2. 从右往左扫描数组。每次扫描到一个元素 x，先查询已经出现过的、值小于 x 的元素个数，即query(x - 1)。
3. 将这个 x 的出现次数加 1，执行add(x, 1)。

因为是从右往左扫描，所以已经出现过的元素都在当前元素的右侧。如果它们值小于当前值，且下标大于当前下标，就构成逆序对。

7.2 离散化步骤

如果原数组的值域很大（比如 10^9），不能直接开这么大的树状数组，必须先离散化。

离散化流程：

vector<int> all = nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int &x : nums) { x = lower_bound(all.begin(), all.end(), x) - all.begin() + 1; }

排序去重后，每个数值都有了唯一的“排名”，排名范围是 1 到 m，m 是不同数值的个数。

7.3 完整 C++ 代码

// 文件路径：inversion.cpp #include <bits/stdc++.h> using namespace std; int lowbit(int x) { return x & -x; } long long countInversions(vector<int> nums) { // 1. 离散化 vector<int> all = nums; sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); for (int &x : nums) { x = lower_bound(all.begin(), all.end(), x) - all.begin() + 1; } int m = all.size(); vector<int> tree(m + 1, 0); auto add = [&](int idx, int delta) { while (idx <= m) { tree[idx] += delta; idx += lowbit(idx); } }; auto query = [&](int idx) { int res = 0; while (idx > 0) { res += tree[idx]; idx -= lowbit(idx); } return res; }; long long ans = 0; for (int i = nums.size() - 1; i >= 0; --i) { ans += query(nums[i] - 1); add(nums[i], 1); } return ans; } int main() { vector<int> nums = {5, 3, 2, 4, 1}; cout << countInversions(nums) << endl; return 0; }

7.4 运行结果说明

数组 [5, 3, 2, 4, 1] 中的逆序对包括：

(5,3) (5,2) (5,4) (5,1) (3,2) (3,1) (2,1) (4,1)

共 8 对，程序输出为 8。可以通过手算验证。

7.5 为什么这种方法不会超时

每个元素在从右往左扫描时，只执行一次query和一次add，两者都是 O(log m)，所以总复杂度是 O(n log n)。这个复杂度对于 n = 10^5 甚至 n = 10^6 的题目都能在合理时间内完成。

8. 进阶实战：树状数组上二分找第 k 小

8.1 问题描述与思路

有一类问题需要动态维护一个集合，并支持查询当前集合中第 k 小的元素。如果集合中元素的值域不大，可以用树状数组维护每个值的出现次数，然后通过“树状数组上二分”快速定位第 k 小。

这里的核心思想是二进制倍增：从高位开始尝试跳跃，如果当前跳到的节点值小于 k，说明第 k 小在更后面，于是跳过去并减去该节点值；否则不跳。

前提条件：树状数组维护的是非负频次，且所有更新都是非负操作。

8.2 完整 C++ 代码

// 文件路径：kth.cpp #include <bits/stdc++.h> using namespace std; class FenwickTree { private: vector<int> tree; int n; int lowbit(int x) { return x & -x; } public: FenwickTree(int size) : n(size) { tree.resize(n + 1, 0); } void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += lowbit(idx); } } int query(int idx) { int res = 0; while (idx > 0) { res += tree[idx]; idx -= lowbit(idx); } return res; } // 找到前缀和 >= k 的最小下标 int kth(int k) { int idx = 0; int maxPow = 1; while (maxPow << 1 <= n) { maxPow <<= 1; } for (int step = maxPow; step > 0; step >>= 1) { int next = idx + step; if (next <= n && tree[next] < k) { idx = next; k -= tree[next]; } } return idx + 1; } }; int main() { FenwickTree bit(8); vector<int> nums = {1, 1, 2, 2, 3, 4, 4, 4}; for (int x : nums) { bit.add(x, 1); } cout << bit.kth(1) << endl; cout << bit.kth(3) << endl; cout << bit.kth(8) << endl; return 0; }

8.3 运行结果与解释

输出：

1 2 4

解释：

• 第 1 小元素是 1，对应下标 1。
• 第 3 小元素：频次累积到 3 时，已经包含了两个 1 和一个 2，所以答案是 2。
• 第 8 小元素：所有数都累加完，最后一个是 4。

8.4 倍增时为什么从最高位 2 的幂开始

树状数组的节点 c[i] 天然覆盖长度为lowbit(i)的区间。如果我们用倍增的方式构建“跳跃路径”，每个 step 都是 2 的幂，恰好对应树状数组某个层级上的区间长度。这样能保证每次跳跃后，idx + step不会跳到重复覆盖的区域，从而正确累加频次。

这种操作同样只要 O(log n) 次，因为 step 从最大 2 的幂逐次减半到 1。

9. 常见问题与排查思路

9.1 树状数组的常见错误

9.2 排查建议

在调试树状数组题目时，建议先写一个非常小的数组（比如 n = 8），手动模拟一遍更新和查询的节点路径，然后与程序输出对比。树状数组的问题通常集中在“方向写反”和“边界写错”这两类，只要把这两点排查清楚，大部分问题都能解决。

另外，可以在本地用暴力前缀和做对拍：

for (int i = 1; i <= n; ++i) { int sum = 0; for (int j = 1; j <= i; ++j) sum += a[j]; assert(sum == bit.query(i)); }

一旦发现不一致，用二分定位出错位置，效率会高很多。

10. 最佳实践与工程建议

10.1 封装成结构体或类

尽量不要把树状数组的数组和操作散落在主函数里。封装成FenwickTree结构体或类之后，多个测试用例之间创建新的对象即可，不会互相污染数据。在 C++ 中，建议将tree作为私有成员，外部只能通过add和query操作。

10.2 全局数组和局部数组的选择

在算法竞赛中，为了效率，很多人会直接用全局数组。但在工程实践中，更推荐封装。两者的权衡在于：

• 全局数组：速度快，写起来简单，但多组测试时容易忘记清空。
• 封装对象：代码清晰，不易出错，代价是少量函数调用开销。

对于绝大多数题目，封装对象不会导致性能问题。

10.3 时间复杂度要心里有数

树状数组的 O(log n) 非常稳定，但要注意常数。每次add和query的循环次数并不是 log2(n)，而是更接近“二进制中 1 的个数”。当 n = 10^5 时，单次操作通常不到 20 次循环，这是它比线段树更快的原因之一。

10.4 结合差分的扩展用法

树状数组不只支持单点更新、区间查询。如果配合差分数组，可以实现区间更新、单点查询，甚至区间更新、区间查询。后者需要维护两个树状数组，但核心原理仍然不变。建议在掌握基础模板后，把差分的扩展用法也练习一遍，这样能把树状数组用到更多题目场景中。

10.5 一个很实用的建议

学习树状数组时，不要只背模板，一定要自己手动模拟一次 8 或 16 的完整二进制路径。把下面这张表亲手算一遍：

i = 1, lowbit = 1 i = 2, lowbit = 2 i = 3, lowbit = 1 i = 4, lowbit = 4 i = 5, lowbit = 1 i = 6, lowbit = 2 i = 7, lowbit = 1 i = 8, lowbit = 8

然后再模拟add(3, delta)和query(7)的节点路径。这个过程只需要十分钟，但理解深度远超看十篇文章。很多后来写线段树、Splay 平衡树、可持久化线段树的同学，都是从树状数组的这套二进制分解中获得了对“区间划分”的直觉。希望这篇文章也能帮你打通这一层。如果觉得有用，可以收藏备用，写题的时候拿出来对照。