企业官网建设流程全解析

大家好，我是你们的老朋友。

在刷算法题和准备面试的过程中，有一个数据结构几乎绕不开，那就是树状数组。很多同学第一次接触它时，会被“树状”“数组”这两个词搞懵：它到底是一棵树还是一个数组？为什么代码看起来只有短短几行，却能高效解决区间求和、逆序对等问题？

本文将系统拆解树状数组，内容包括：核心概念、原理推导、基础模板、典型应用（逆序对）、进阶技巧（树状数组上二分、区间修改），以及常见的坑点和排查思路。无论你是算法竞赛入门选手，还是在为面试刷题，这篇文章都能给你一套完整、可直接落地的实战参考。

1. 先搞清楚树状数组是什么

1.1 它解决什么问题

先来看一个非常常见的场景。假设你有一个长度为n的数组a，需要支持下面两种操作：

• 单点修改：把a[i]加上一个值v。
• 区间查询：求a[l] + a[l+1] + ... + a[r]的和，也就是区间和。

如果用普通数组，单点修改是O(1)的，但区间查询最坏是O(n)；如果预处理前缀和数组，区间查询能到O(1)，但单点修改又变成O(n)。

当操作次数达到10^5甚至10^6时，无论哪种方案都扛不住。树状数组就是用来平衡这两种操作的：它能把单点修改和区间查询都做到O(log n)。

树状数组也叫Fenwick Tree或二叉索引树（Binary Indexed Tree, BIT）。它用一段普通数组，通过下标二进制表示中的规律，维护出一棵逻辑上的“树”，从而实现高效的动态前缀和运算。

1.2 树状数组 vs 前缀和 vs 线段树

为了不混淆，我们把这几个概念放在一起对比：

简要总结：如果题目只有查询没有修改，直接前缀和就好；如果涉及单点修改和区间求和，树状数组是最优候选；如果涉及区间乘、区间染色等更复杂的操作，再考虑线段树。

1.3 典型应用场景

树状数组的实际应用非常广，下面这些场景都很常见：

• 求一个数组的逆序对数量。
• 维护动态数据流中的前缀和/区间和。
• 求数组中第 k 小元素（配合树状数组上二分）。
• 处理差分数组 + 区间修改。
• 在竞赛题中用于离散化后的频次统计。

掌握了树状数组之后，很多看起来复杂的问题都能用非常简洁的代码解决。这也是为什么算法竞赛选手几乎人手一份树状数组模板的原因。

2. 环境准备与语言选择

2.1 运行环境

树状数组本身是数据结构，不依赖任何特殊框架。只要你的电脑能运行 C++、Java 或 Python，就能直接编写和测试。本文示例以C++为主，同时给出Python和Java的版本，方便不同语言使用者对照。

• 操作系统：Windows / macOS / Linux 均可。
• 编译器：GCC（C++）、JDK 8+（Java）、Python 3.6+。
• IDE：Visual Studio Code、CLion、IDEA、PyCharm 都可以，重点是在本地能跑起来。

版本不是核心，重点理解算法思路。下面示例默认在一个拥有标准库的常规开发环境中运行。

2.2 示例项目结构

我建议把树状数组封装成类或结构体，方便在多个题目中复用。示例目录结构如下：

fenwick-demo/ ├── Main.cpp # C++ 演示代码 ├── Fenwick.py # Python 演示代码 └── Main.java # Java 演示代码

在刷题平台（如 LeetCode、牛客、洛谷）使用时，一般只需要把核心类复制到提交代码中即可。

3. 树状数组核心原理拆解

3.1 它为什么要叫“树状数组”

从存储角度看，树状数组确实就是一个数组tree[]。但它的下标关系形成了一棵逻辑树，而这个逻辑树的关键是lowbit运算。

lowbit 的定义是：

lowbit(x) = x & (-x)

这个运算能取出x的二进制表示中最低位的1所代表的值。

举个例子：

• x = 6，二进制是110，-6的补码是010，所以6 & (-6) = 2。也就是说lowbit(6) = 2。
• x = 8，二进制是1000，lowbit(8) = 8。
• x = 7，二进制是111，lowbit(7) = 1。

lowbit 确定了树状数组中每个节点“管”的范围。

3.2 树状数组的存储结构

约定数组下标从1开始。对于下标i，树状数组节点tree[i]管理的是原数组区间：

[i - lowbit(i) + 1, i]

也就是说，tree[i]存的是原数组从i - lowbit(i) + 1到i的和。

举几个具体例子：

可以发现，tree[4]直接管了整个区间[1, 4]，而tree[3]只管自己。这种规律决定了我们修改和查询时的路径长度都是O(log n)。

3.3 单点修改：update 操作

如果我们把原数组下标pos的值增加x，那么所有管理了pos的树状数组节点都要同步更新。

更新的方法是：

i = pos while (i <= n) { tree[i] += x i += lowbit(i) }

为什么是i += lowbit(i)？

从二进制角度看，i + lowbit(i)会消去i最右边连续的一串1，并把更高一位的0变成1，相当于往“父节点”方向移动。这样跳过的每个节点都恰好覆盖当前位置。

继续用例子说明。假设n = 8，修改pos = 3：

• i = 3，更新tree[3]，然后i = 3 + lowbit(3) = 3 + 1 = 4；
• i = 4，更新tree[4]，然后i = 4 + lowbit(4) = 4 + 4 = 8；
• i = 8，更新tree[8]，然后i = 16 > n，结束。

所以修改pos=3时，需要更新tree[3]、tree[4]、tree[8]。这个路径长度是O(log n)。

3.4 前缀和查询：query 操作

查询[1, pos]的和，方法是从pos开始，不断累加tree[i]，然后向左跳跃：

res = 0 i = pos while (i > 0) { res += tree[i] i -= lowbit(i) }

为什么是i -= lowbit(i)？

因为tree[i]管的是[i - lowbit(i) + 1, i]，累加完当前节点后，需要去下一个更大的区间，也就是执行i = i - lowbit(i)。

继续用例子说明。查询pos = 7：

• i = 7，累加tree[7]，然后i = 7 - lowbit(7) = 6；
• i = 6，累加tree[6]，然后i = 6 - lowbit(6) = 4；
• i = 4，累加tree[4]，然后i = 0，结束。

结果等于tree[7] + tree[6] + tree[4]，正好覆盖了区间[1, 7]。

如果要求[l, r]的区间和，可以用：

sum(l, r) = query(r) - query(l - 1)

这个思路本质上和前缀和数组相同，但这里的query每次都是动态计算的。这个实现方式让人容易混淆的点在于：树状数组的查询是前缀和查询，不是直接区间查询。所以query(r) - query(l-1)这一转换需要牢记。

4. 基础模板：从零实现一个树状数组

4.1 C++ 模板

以下是一个最基础的树状数组模板，封装了update和query两个核心操作。

// 文件路径：Main.cpp #include <bits/stdc++.h> using namespace std; class Fenwick { private: int n; vector<int> tree; public: Fenwick(int n) : n(n), tree(n + 1, 0) {} // 单点修改：把下标 pos 增加 delta void update(int pos, int delta) { while (pos <= n) { tree[pos] += delta; pos += pos & (-pos); } } // 前缀和查询：[1, pos] 的和 int query(int pos) { int res = 0; while (pos > 0) { res += tree[pos]; pos -= pos & (-pos); } return res; } // 区间和查询：[l, r] 的和 int rangeQuery(int l, int r) { return query(r) - query(l - 1); } }; int main() { vector<int> a = {0, 1, 3, 5, 7, 9}; // 下标从 1 开始，第 0 位占位 Fenwick fw(5); for (int i = 1; i <= 5; i++) { fw.update(i, a[i]); } cout << "sum [2, 4] = " << fw.rangeQuery(2, 4) << endl; // 3 + 5 + 7 = 15 fw.update(3, 10); // a[3] 从 5 变成 15 cout << "sum [2, 4] = " << fw.rangeQuery(2, 4) << endl; // 3 + 15 + 7 = 25 return 0; }

运行结果：

sum [2, 4] = 15 sum [2, 4] = 25

这里有几个细节：

• 数组下标从1开始，所以vector<int> a第0位用来占位，不参与计算。
• pos & (-pos)就是 lowbit，在 C++ 中可以直接这样写。
• rangeQuery(l, r)需要保证1 <= l <= r <= n。

4.2 Python 模板

Python 版本思路一致，只是用类来封装。

# 文件路径：Fenwick.py class Fenwick: def __init__(self, n: int): self.n = n self.tree = [0] * (n + 1) def update(self, pos: int, delta: int) -> None: while pos <= self.n: self.tree[pos] += delta pos += pos & (-pos) def query(self, pos: int) -> int: res = 0 while pos > 0: res += self.tree[pos] pos -= pos & (-pos) return res def range_query(self, l: int, r: int) -> int: return self.query(r) - self.query(l - 1) if __name__ == "__main__": a = [0, 1, 3, 5, 7, 9] fw = Fenwick(5) for i in range(1, 6): fw.update(i, a[i]) print("sum [2, 4] =", fw.range_query(2, 4)) fw.update(3, 10) print("sum [2, 4] =", fw.range_query(2, 4))

执行结果与 C++ 版本一致。

4.3 Java 模板

// 文件路径：Main.java public class Main { static class Fenwick { int n; int[] tree; Fenwick(int n) { this.n = n; this.tree = new int[n + 1]; } void update(int pos, int delta) { while (pos <= n) { tree[pos] += delta; pos += pos & (-pos); } } int query(int pos) { int res = 0; while (pos > 0) { res += tree[pos]; pos -= pos & (-pos); } return res; } int rangeQuery(int l, int r) { return query(r) - query(l - 1); } } public static void main(String[] args) { int[] a = {0, 1, 3, 5, 7, 9}; Fenwick fw = new Fenwick(5); for (int i = 1; i <= 5; i++) { fw.update(i, a[i]); } System.out.println("sum [2, 4] = " + fw.rangeQuery(2, 4)); fw.update(3, 10); System.out.println("sum [2, 4] = " + fw.rangeQuery(2, 4)); } }

4.4 复杂度分析

• 单次update：O(log n)。
• 单次query：O(log n)。
• 建树：对每个元素执行一次update，总复杂度O(n log n)。

如果n = 10^5，log n约等于17，性能完全能承受。即使n = 10^6，几十次操作的复杂度也能控制在百万级别。

需要注意的是，如果输入数据很大，可以采用O(n)建树而不是循环update，但作为模板题，O(n log n)建树已经足够。在算法竞赛中，10^5级别的数据量用O(n log n)完全没问题。

5. 完整实战：逆序对计数

5.1 逆序对定义

给定数组a，如果i < j且a[i] > a[j]，则称(i, j)为一个逆序对。逆序对的数量常用于衡量数组的有序程度。

例如数组[3, 1, 2]，逆序对有两个：(3, 1)和(3, 2)。

如果把a[i]看成数值大小，那么逆序对本质上就是统计“有多少个在右边但比当前数小”的元素个数。

5.2 暴力思路

最直接的方法是双重循环：

int countInversions(vector<int>& a) { int n = a.size(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j]) ans++; } } return ans; }

这个方法时间复杂度是O(n^2)，当n = 10^5时会严重超时。因此需要更高效的方法。

5.3 树状数组求逆序对思路

利用树状数组的经典套路如下：

1. 把原数组元素按数值大小离散化，把原来可能很大的值映射到1..m。
2. 从右往左遍历原数组，先查询比当前元素小的元素个数：

   query(a[i] - 1)

   这个值就是在当前元素右边、比当前元素小的元素数量，也就是以当前元素为“左端点”的逆序对数量。
3. 将当前元素加入树状数组：

   update(a[i], 1)

4. 累加所有查询结果，得到总逆序对数。

如果从左往右遍历，查询query(a[i] - 1)得到的是已出现过的比当前元素小的数量，需要通过已遍历个数 - query(a[i])才能获得比当前元素大的数量。两种方式都可以，但从右往左写起来更直观。

5.4 为什么要离散化

树状数组的下标必须是正整数且不能太大。如果原数组值是10^9，直接开10^9的数组不现实。离散化就是先把所有出现的数值排序去重，然后映射成连续的排名。

例如原数组[1e9, 1, 500]，排序去重后是[1, 500, 1e9]，映射为[3, 1, 2]。这样树状数组的大小只需要3。

5.5 完整代码实现

// 文件路径：Main.cpp #include <bits/stdc++.h> using namespace std; class Fenwick { private: int n; vector<int> tree; public: Fenwick(int n) : n(n), tree(n + 1, 0) {} void update(int pos, int delta) { while (pos <= n) { tree[pos] += delta; pos += pos & (-pos); } } int query(int pos) { int res = 0; while (pos > 0) { res += tree[pos]; pos -= pos & (-pos); } return res; } }; long long countInversions(vector<int>& nums) { // 离散化 vector<int> sortedNums = nums; sort(sortedNums.begin(), sortedNums.end()); sortedNums.erase(unique(sortedNums.begin(), sortedNums.end()), sortedNums.end()); int m = sortedNums.size(); Fenwick fw(m); long long ans = 0; // 从右往左遍历 for (int i = nums.size() - 1; i >= 0; i--) { // 当前元素在离散化后的排名，从 1 开始 int rank = lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]) - sortedNums.begin() + 1; // 查询比当前元素小的个数 ans += fw.query(rank - 1); // 当前元素加入 fw.update(rank, 1); } return ans; } int main() { vector<int> a = {3, 1, 2}; cout << "逆序对数量: " << countInversions(a) << endl; // 2 vector<int> b = {5, 4, 3, 2, 1}; cout << "逆序对数量: " << countInversions(b) << endl; // 10 return 0; }

5.6 运行结果说明

逆序对数量: 2 逆序对数量: 10

对于数组[5, 4, 3, 2, 1]，任意两对都构成逆序对，数量是5 * 4 / 2 = 10，结果正确。

通过树状数组，我们把时间复杂度从O(n^2)降到了O(n log n)，空间复杂度为O(n)。

6. 进阶：树状数组上二分

6.1 什么是“树状数组上二分”

“树状数组上二分”指的是在树状数组维护的频次数组上，查询第 k 小元素，在很多计数类题目里非常常见。它的本质是利用树状数组的二进制结构做类似“二分查找”的操作，时间复杂度从普通二分加查询的O(log^2 n)降到O(log n)。

典型场景是：维护一个可重复元素的集合，支持插入、删除，并查询第k小的元素。例如在线处理数据流、求动态数组的中位数等。

6.2 普通二分的问题

假设我们在树状数组里维护每个数值的出现次数。要找到第k小的元素，最简单的方法是二分值域：

int l = 1, r = n, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (fw.query(mid) >= k) { ans = mid; r = mid - 1; } else { l = mid + 1; } }

每次二分需要一次query，复杂度是O(log n)，所以总复杂度是O(log^2 n)。这个复杂度通常也能通过，但在数据量很大或者需要频繁操作时，树状数组上二分能更进一步。

6.3 树状数组上二分的原理

树状数组的tree[i]管理区间[i - lowbit(i) + 1, i]，并且lowbit(i)正好是区间长度。我们可以用一个pos变量，从高到低枚举二进制位，尝试累加节点。

思路是：

pos = 0 当前累计和 sum = 0 for (step = 2^(floor(log2(n))); step >= 1; step >>= 1): next = pos + step if next <= n and sum + tree[next] < k: sum += tree[next] pos = next 最后答案是 pos + 1

这样做为什么有效？因为当我们试到某个next时，tree[next]管的是[next - lowbit(next) + 1, next]。如果pos恰好是next - lowbit(next)，那么加上tree[next]之后，sum就是[1, next]的前缀和。通过判断这个前缀和是否小于k，可以确定第k小的数是否大于next。

6.4 完整示例：第 k 小元素

// 文件路径：Main.cpp #include <bits/stdc++.h> using namespace std; class Fenwick { private: int n; vector<int> tree; public: Fenwick(int n) : n(n), tree(n + 1, 0) {} void update(int pos, int delta) { while (pos <= n) { tree[pos] += delta; pos += pos & (-pos); } } int query(int pos) { int res = 0; while (pos > 0) { res += tree[pos]; pos -= pos & (-pos); } return res; } // 查询第 k 小元素，k 从 1 开始 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 next = pos + step; if (next <= n && tree[next] < k) { k -= tree[next]; pos = next; } } return pos + 1; } }; int main() { Fenwick fw(10); // 插入元素：1 出现 2 次，2 出现 3 次，3 出现 4 次 fw.update(1, 2); fw.update(2, 3); fw.update(3, 4); cout << "第 1 小: " << fw.kth(1) << endl; // 1 cout << "第 2 小: " << fw.kth(2) << endl; // 1 cout << "第 3 小: " << fw.kth(3) << endl; // 2 cout << "第 6 小: " << fw.kth(6) << endl; // 3 return 0; }

输出：

第 1 小: 1 第 2 小: 1 第 3 小: 2 第 6 小: 3

这里需要注意：tree[next] < k判断的是“前缀和严格小于 k”时向右移动。因为我们要找的是满足query(pos + 1) >= k的最小pos + 1，所以当query(next) < k时，说明答案比当前next更靠右，于是移动pos并减去tree[next]。

这种写法可以应用于带修改的动态数组中求第k小，比如在线统计字符数量、实时排行榜分数等。

7. 进阶：区间修改与区间查询

7.1 区间修改 + 单点查询

如果用树状数组维护原数组的差分数组diff[i] = a[i] - a[i-1]，那么对原数组区间[l, r]加上v，等价于：

diff[l] += v diff[r + 1] -= v

单点查询a[i]等价于：

prefixSum(diff, i)

这本质是把原问题转换为“单点修改 + 前缀和查询”，正好是树状数组的强项。代码非常简单，这里不再重复展开。

7.2 区间修改 + 区间查询

如果同时要求区间修改和区间求和，单个差分树状数组就不够了。这里需要维护两个树状数组。

推导如下：

设原数组为a，差分数组为d，即d[i] = a[i] - a[i-1]，且d[1] = a[1]。

对于前缀和S(x) = sum_{i=1}^{x} a[i]，有：

S(x) = sum_{i=1}^{x} sum_{j=1}^{i} d[j] = sum_{j=1}^{x} d[j] * (x - j + 1) = (x + 1) * sum_{j=1}^{x} d[j] - sum_{j=1}^{x} j * d[j]

所以只要用两个树状数组分别维护：

• BIT1：维护d[i]的前缀和。
• BIT2：维护i * d[i]的前缀和。

区间和[l, r]就是：

S(r) - S(l - 1)

7.3 完整代码示例

// 文件路径：Main.cpp #include <bits/stdc++.h> using namespace std; class FenwickRange { private: int n; vector<long long> bit1; // 维护 d[i] vector<long long> bit2; // 维护 i * d[i] void internalUpdate(vector<long long>& bit, int pos, long long delta) { while (pos <= n) { bit[pos] += delta; pos += pos & (-pos); } } long long internalQuery(vector<long long>& bit, int pos) { long long res = 0; while (pos > 0) { res += bit[pos]; pos -= pos & (-pos); } return res; } public: FenwickRange(int n) : n(n), bit1(n + 1, 0), bit2(n + 1, 0) {} // 区间修改：[l, r] 加上 delta void rangeUpdate(int l, int r, long long delta) { internalUpdate(bit1, l, delta); internalUpdate(bit1, r + 1, -delta); internalUpdate(bit2, l, delta * l); internalUpdate(bit2, r + 1, -delta * (r + 1)); } // 前缀和：[1, x] long long prefixSum(int x) { return (x + 1) * internalQuery(bit1, x) - internalQuery(bit2, x); } // 区间和：[l, r] long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } }; int main() { FenwickRange fw(5); // 初始数组：[1, 2, 3, 4, 5] for (int i = 1; i <= 5; i++) { fw.rangeUpdate(i, i, i); } cout << "sum [1, 5] = " << fw.rangeSum(1, 5) << endl; // 15 fw.rangeUpdate(2, 4, 10); // 数组变为 [1, 12, 13, 14, 5] cout << "sum [2, 4] = " << fw.rangeSum(2, 4) << endl; // 39 cout << "sum [1, 5] = " << fw.rangeSum(1, 5) << endl; // 45 return 0; }

输出：

sum [1, 5] = 15 sum [2, 4] = 39 sum [1, 5] = 45

这种方式可以支持大规模的区间加法和区间求和，代码量比线段树小很多，是竞赛中的常用优化方案。

8. 常见问题与排查思路

在实际使用树状数组时，新手经常遇到各种问题。下面整理一份排查清单。

8.1 一个容易踩坑的低级错误

如果你在update时写了下面的代码：

void update(int pos, int delta) { while (pos <= n) { tree[pos] += delta; pos += pos & (-pos); } }

当pos = 0时，pos & (-pos) = 0，pos永远不变，程序会死循环。所以在代码入口处可以加一行：

if (pos <= 0) return;

8.2 什么时候用树状数组，什么时候用线段树

这个问题非常高频。我的建议是：

• 只要题目支持“单点修改 + 区间查询”或“差分 + 区间修改”，优先使用树状数组，因为代码量小、常数小。
• 如果涉及区间最大值、区间最小值、区间染色的懒标记等复杂操作，才考虑线段树。
• 如果题目同时要求“区间取反”“区间赋值”等操作，树状数组基本无法实现，只能线段树或分块。

9. 最佳实践与工程建议

9.1 封装成通用类

在实际项目或刷题中，不要把树状数组操作散落在主函数里。建议封装成类或结构体，对外只暴露update、query、kth等方法。这样代码复用性高，也不容易在边界条件上出错。

9.2 明确数据类型

树状数组内部维护的数据可能是频次、区间和、乘积等。如果累加结果可能超过2^31 - 1，建议直接使用long long或long，避免后续排查溢出浪费时间。

9.3 离散化模板固定化

很多题目都需要离散化，建议把离散化过程固定为模板：

vector<int> sortedNums = nums; sort(sortedNums.begin(), sortedNums.end()); sortedNums.erase(unique(sortedNums.begin(), sortedNums.end()), sortedNums.end()); auto getId = [&](int x) { return lower_bound(sortedNums.begin(), sortedNums.end(), x) - sortedNums.begin() + 1; };

这样写既清晰又能避免每次重复计算。

9.4 多测数据注意重置

树状数组在每次测试用例前必须重置为初始状态。如果不想memset整个数组，可以直接重新new一个对象。

9.5 生产环境中的“最小权限”意识

虽然树状数组主要面向算法场景，但任何会修改数组中数据的代码，都建议先在小数据量上验证逻辑，再用于大数据集。尤其在业务系统中，如果你用树状数组维护统计指标，要确保数据修改的边界条件正确，避免因为下标错误导致线上数据被污染。核心思路是：先在本地测试环境中跑通，确认结果后再部署。

10. 总结

通过本文，你应该已经掌握了树状数组的完整知识链路：

• 它是什么：一种支持单点修改和区间查询的树形数据结构。
• 它为什么快：通过 lowbit 运算把修改和查询收敛到O(log n)。
• 基本操作：update和query。
• 经典应用：求逆序对、维护动态前缀和、差分区间修改。
• 进阶技巧：树状数组上二分求第 k 小、双树状数组实现区间修改与区间查询。
• 常见坑点：下标从 1 开始、防止死循环、离散化去重、使用long long防溢出。

下一步，你可以尝试在 LeetCode 和洛谷上搜索“树状数组”“逆序对”“第 k 小”相关题目，把本文模板套进去做几道题，体会它的威力。等到熟练之后，再接触线段树时，你会觉得很多思路是相通的。

如果你觉得这篇文章对你有帮助，欢迎点赞收藏，也欢迎在评论区交流你遇到的树状数组问题。