企业官网建设流程全解析

之前在算法训练中反复使用树状数组解决区间求和、动态排名等问题，发现网上资料虽然多，但往往只讲模板，不讲为什么这样写。遇到区间修改、逆序对、树上二分这些进阶场景时，零零散散翻了不少文章才拼出完整思路。这篇文章把树状数组从原理到高阶应用做一次系统梳理，包含完整的代码模板、复杂度分析和踩坑记录，竞赛选手和准备面试的开发者都可以直接参考。

1. 树状数组是什么

1.1 树状数组解决什么问题

树状数组（Binary Indexed Tree，BIT）是一种用于维护数列前缀和、支持单点修改和区间查询的数据结构。它由 Peter M. Fenwick 在 1994 年提出，因此也叫 Fenwick Tree。

先看一个经典场景：维护一个长度为n的数组，需要支持两类操作：

1. 修改某个位置的值，例如a[i] += x。
2. 查询区间[l, r]的和。

如果只用普通数组，修改是O(1)，查询需要遍历区间，最坏是O(n)。如果预处理前缀和数组，那么查询是O(1)，但修改需要更新后面所有位置的前缀和，最坏是O(n)。

当n很大、操作次数很多时，这两种做法都不够高效。树状数组用二进制思想把两种操作都优化到O(log n)，实现代码又非常短，只有十几行，因此成为算法竞赛和工程开发中非常常用的数据结构。

1.2 树状数组和线段树的区别

很多初学者会问：有了线段树，为什么还要学树状数组？

两者确实都能处理区间查询和单点修改，但有明显差异：

一句话总结：树状数组能解决的问题，是线段树的子集，但树状数组实现简单、常数小，能用树状数组时优先用树状数组。遇到需要维护区间最值、区间最大子段和等复杂信息时，再上线段树。

2. 环境准备与版本说明

树状数组是纯算法逻辑，不依赖特定编程语言版本或操作系统。只要支持数组和基础位运算，就能实现。下面以最常见的学习环境为例：

• 编程语言：C++（竞赛最常用）、Java、Python 均可
• 编译环境：C++11 及以上，或者任意 Python 3.x
• 开发工具：Visual Studio Code、CLion、Dev-C++、或直接在在线判题系统上编写

本文的示例以 C++ 为主，同时也给出 Python 版本作为参考。算法本身在任何语言下思路完全一致，只是语法不同。

如果本地需要验证，建议建一个简单的控制台项目即可，不需要额外安装库。核心代码只有一个数组和两个函数。

3. 树状数组的核心原理

3.1 lowbit 运算

树状数组的第一个关键概念是lowbit。

lowbit(x)表示正整数x的二进制表达式中，最低位的1所对应的数值。例如：

• x = 6，二进制为110，最低位的1对应10，即2，所以lowbit(6) = 2。
• x = 8，二进制为1000，最低位的1对应1000，即8，所以lowbit(8) = 8。
• x = 5，二进制为101，最低位的1对应1，所以lowbit(5) = 1。

计算lowbit的公式很简单：

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

为什么x & (-x)能得到最低位的1？因为在补码表示中，-x等于~x + 1。~x把所有位取反，加 1 后，x最低位的1所在位置及其右边保持不变，更高位全部取反。这样x & (-x)的二进制结果恰好只保留了最低位的1。

这个运算虽然只有一行，但它是树状数组所有操作的基石。

3.2 树状结构的设计思想

树状数组维护的并不是原数组本身，而是一个基于二进制分解的累加结构。

设原数组为a[1..n]，树状数组为t[]。树状数组的第i个位置t[i]存储的是原数组中某一特定区间的和。具体规则：

t[i] = sum(a[i - lowbit(i) + 1 .. i])

也就是说，t[i]管理的是从i - lowbit(i) + 1到i这个长度为lowbit(i)的区间和。

举个例子，假设n = 8，那么：

• t[1] = a[1]，因为lowbit(1) = 1
• t[2] = a[1] + a[2]，因为lowbit(2) = 2
• t[3] = a[3]，因为lowbit(3) = 1
• t[4] = a[1] + a[2] + a[3] + a[4]，因为lowbit(4) = 4
• t[5] = a[5]
• t[6] = a[5] + a[6]
• t[7] = a[7]
• t[8] = a[1] + ... + a[8]

可以看到，下标为奇数的位置只存原数组对应位置的值；下标为 2 的幂次的位置存的是一个前缀和。

这种设计有一个重要性质：从任意位置i往前求和时，只需要不断减去lowbit(i)，就能覆盖到所有需要累加的区间，且不重不漏。

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

树状数组的修改操作中，下标更新方式是i += lowbit(i)；查询操作中，下标更新方式是i -= lowbit(i)。

这两种操作的本质都是二进制位的变化。每次加或减lowbit，都会把二进制中最低位的1消除或进位。由于一个整数最多有O(log n)个二进制位，所以操作次数不会超过O(log n)。

这也是树状数组高效的根本原因：它利用二进制的结构，把区间信息切分成若干个长度恰好是2的幂的子区间，任何前缀都能用这些子区间拼出来。

4. 树状数组的基本操作详解

4.1 单点修改操作

单点修改的目的是让原数组某个位置的值变化，同时更新所有包含该位置的树状数组节点。比如原数组a[i]增加了x，那么所有管理范围覆盖i的t[j]都要加上x。

这些j的规律是：

j = i; while (j <= n) { t[j] += x; j += lowbit(j); }

从i开始，不断加上自身的lowbit，就能依次找到所有父节点。

举个例子，如果修改a[3]，那么需要更新t[3]、t[4]、t[8]，因为：

• lowbit(3) = 1，3 + 1 = 4
• lowbit(4) = 4，4 + 4 = 8

这三个位置的管理范围确实都包含下标3。

4.2 前缀和查询

查询1到pos的和时，从pos开始，不断累加t[pos]，然后pos -= lowbit(pos)。

int query(int pos) { int sum = 0; while (pos > 0) { sum += t[pos]; pos -= lowbit(pos); } return sum; }

比如查询1到6的和：

• pos = 6，累加t[6]，它管理a[5] + a[6]
• pos = 6 - lowbit(6) = 4，累加t[4]，它管理a[1] + a[2] + a[3] + a[4]
• pos = 4 - lowbit(4) = 0，停止

所以query(6) = t[6] + t[4]，正好等于a[1]到a[6]的总和。

4.3 区间和查询

有了前缀和，区间[l, r]的和可以转换为两个前缀和相减：

int rangeQuery(int l, int r) { return query(r) - query(l - 1); }

这里要注意下标从 1 开始，因为lowbit(0)没有意义，树状数组的循环依赖下标为正数。如果原数组从 0 开始，需要把所有下标整体加 1。

5. 完整实战：单点修改 + 区间查询

5.1 问题描述

给定一个长度为n的数组，初始值为a[1..n]。接下来有m次操作，分成两类：

• 1 i x：把a[i]增加x
• 2 l r：查询区间[l, r]的和

其中1 <= n, m <= 100000。

这是树状数组最基础的模板题，适合作为第一个完整练习。

5.2 C++ 完整实现

文件路径：main.cpp

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, m; long long t[MAXN]; int lowbit(int x) { return x & (-x); } void add(int i, int x) { while (i <= n) { t[i] += x; i += lowbit(i); } } long long query(int pos) { long long res = 0; while (pos > 0) { res += t[pos]; pos -= lowbit(pos); } return res; } long long rangeQuery(int l, int r) { return query(r) - query(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; add(i, x); } while (m--) { int op, a, b; cin >> op >> a >> b; if (op == 1) { add(a, b); } else { cout << rangeQuery(a, b) << '\n'; } } return 0; }

这里把t[]定义为long long，是因为区间和可能超过int范围，尤其是多次累加之后。用long long可以避免不必要的溢出问题。

5.3 Python 完整实现

def lowbit(x: int) -> int: return x & (-x) class FenwickTree: def __init__(self, n: int): self.n = n self.t = [0] * (n + 1) def add(self, i: int, x: int) -> None: while i <= self.n: self.t[i] += x i += lowbit(i) def query(self, pos: int) -> int: res = 0 while pos > 0: res += self.t[pos] pos -= lowbit(pos) return res def range_query(self, l: int, r: int) -> int: return self.query(r) - self.query(l - 1) n, m = map(int, input().split()) a = list(map(int, input().split())) bit = FenwickTree(n) for idx, val in enumerate(a, start=1): bit.add(idx, val) for _ in range(m): op, x, y = map(int, input().split()) if op == 1: bit.add(x, y) else: print(bit.range_query(x, y))

5.4 运行验证

输入：

5 4 1 2 3 4 5 2 1 3 1 2 3 2 1 5 2 2 5

第一行表示数组长度n=5，操作次数m=4。初始数组为[1, 2, 3, 4, 5]。

• 查询[1, 3]，和为1 + 2 + 3 = 6
• 将a[2]增加3，数组变为[1, 5, 3, 4, 5]
• 查询[1, 5]，和为18
• 查询[2, 5]，和为5 + 3 + 4 + 5 = 17

预期输出：

6 18 17

6. 进阶实战：区间修改 + 区间查询

6.1 差分思想

上一节处理的是“单点修改 + 区间查询”。如果题目要求“区间修改 + 单点查询”，通常用差分数组配合树状数组解决。

设原数组为a[1..n]，定义差分数组d[i] = a[i] - a[i-1]（a[0] = 0）。那么对a[l..r]区间整体加x，等价于：

d[l] += x d[r + 1] -= x

这样区间修改就变成了差分数列上的两次单点修改。查询某个位置a[i]的值，等价于求差分数组d的前缀和d[1] + d[2] + ... + d[i]。

如果要在区间修改的同时支持区间查询，就需要再多维护一个树状数组。

6.2 维护两个树状数组推导

区间查询的本质是求前缀和S(x) = a[1] + a[2] + ... + a[x]。

用差分表示：

S(x) = sum_{i=1..x} a[i] = sum_{i=1..x} sum_{j=1..i} d[j]

交换求和顺序，发现：

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

因此，只要同时维护两个树状数组：

• b1维护差分数组d[i]
• b2维护i * d[i]的累加结果

就能在O(log n)内完成区间修改和区间查询。

6.3 完整代码实现

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, m; long long b1[MAXN], b2[MAXN]; int lowbit(int x) { return x & (-x); } void update(long long bit[], int i, long long x) { while (i <= n) { bit[i] += x; i += lowbit(i); } } long long query(long long bit[], int i) { long long res = 0; while (i > 0) { res += bit[i]; i -= lowbit(i); } return res; } // 区间 [l, r] 整体增加 x void rangeAdd(int l, int r, long long x) { update(b1, l, x); update(b1, r + 1, -x); update(b2, l, x * (l - 1)); update(b2, r + 1, -x * r); } // 前缀和 S(x) long long prefixSum(int x) { return query(b1, x) * x - query(b2, x); } // 区间和 [l, r] long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; long long last = 0; for (int i = 1; i <= n; i++) { long long cur; cin >> cur; long long d = cur - last; update(b1, i, d); update(b2, i, d * (i - 1)); last = cur; } while (m--) { int op; cin >> op; if (op == 1) { int l, r; long long x; cin >> l >> r >> x; rangeAdd(l, r, x); } else { int l, r; cin >> l >> r; cout << rangeSum(l, r) << '\n'; } } return 0; }

6.4 推导细节说明

区间修改部分，从差分数组的定义出发：

d[l] += x d[r + 1] -= x

对于b2，维护的是i * d[i]：

l 位置增加 x * l r + 1 位置增加 (-x) * (r + 1)

但在实际模板中，很多写法会写成：

update(b2, l, x * (l - 1)); update(b2, r + 1, -x * r);

这里其实是把推导公式化简了，因为prefixSum(x) = x * sum(d[1..x]) - sum(i * d[i])中，x是动态的，无法把x放进差分更新里。用x * (l - 1)和-x * r是为了避免前缀和结果出现常数偏移。建议初学者直接记住这个更新方式，在纸上手动推一次l=2, r=4的例子，就能理解为什么这样更新。

7. 树状数组的高阶应用

7.1 求逆序对

逆序对问题：给定数组a[1..n]，求有多少对(i, j)满足i < j且a[i] > a[j]。

经典做法是归并排序，但树状数组也能高效解决，而且代码更直观。思路：

1. 离散化：把原数组映射为1..k的排名，其中k <= n。
2. 从前往后扫描数组，每遇到一个数x，用树状数组统计当前已经出现过的数中大于x的个数。
3. 把x加入树状数组。

换句话说，遍历到a[i]时，query(n) - query(a[i])就是与a[i]形成逆序对的元素个数。

C++ 实现：

#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; int n; long long t[MAXN]; struct Node { int val, idx; } a[MAXN]; int lowbit(int x) { return x & (-x); } void add(int i, int x) { while (i <= n) { t[i] += x; i += lowbit(i); } } long long query(int i) { long long res = 0; while (i > 0) { res += t[i]; i -= lowbit(i); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].val; a[i].idx = i; } // 按值排序进行离散化 sort(a + 1, a + n + 1, [](const Node& u, const Node& v) { return u.val < v.val; }); vector<int> rank(n + 1); for (int i = 1; i <= n; i++) { rank[a[i].idx] = i; } long long ans = 0; for (int i = 1; i <= n; i++) { ans += query(n) - query(rank[i]); add(rank[i], 1); } cout << ans << '\n'; return 0; }

这里离散化的做法比较直接：先按值排序，再把原数组的每个位置替换为大小排名。如果原值中有重复元素，排序时还需要仔细处理排名规则。实际竞赛题中常用另一种写法：先排序，再用lower_bound或unique去重，再二分映射，这样更简洁。

7.2 树状数组上二分

树状数组不仅可以求和，还能在O(log n)时间内找到前缀和第一次达到某个阈值的位置。这个技巧被称为“树状数组上二分”，常用于处理按权值计数的问题，例如查找第k小元素。

核心思路是：利用树状数组下标二进制的结构，从高位到低位枚举，逐位确定答案。

C++ 实现：

int findKth(int k) { int pos = 0; // 2^LOG 是大于 n 的最大的 2 的幂 for (int i = LOG; i >= 0; i--) { int nxt = pos + (1 << i); if (nxt <= n && t[nxt] < k) { k -= t[nxt]; pos = nxt; } } return pos + 1; }

这个函数的含义是：在树状数组的二进制结构上贪心移动，跳过累加和小于k的块，最终停留的位置就是第k个元素的位置。

但需要注意，这种二分要求树状数组内部维护的是非负的频次计数。如果维护的是前缀和且原数组有负数，这个贪心策略不再保证正确，因为t[]不一定单调递增。

树状数组上二分的典型应用包括：

• 权值线段树的替代方案，支持动态查询第k小
• 在 O(log n) 时间内确定某个累计频次对应的下标
• 解决“前缀和第一个超过k的位置”类问题

7.3 离线查询与二维树状数组

树状数组经常与离线处理结合。例如区间不同数字个数问题，可以把所有查询按右端点排序，边扫描边用树状数组维护每个数字最后一次出现的位置。每次遇到一个数字，就在当前位置加 1，如果之前出现过，就把上次出现位置减 1。这样一个区间[l, r]的不同数字个数就是query(r) - query(l - 1)。

二维树状数组则把一维数组扩展成二维矩阵。修改操作变为双层循环：

void add2D(int x, int y, int val) { for (int i = x; i <= n; i += lowbit(i)) { for (int j = y; j <= m; j += lowbit(j)) { bit[i][j] += val; } } }

二维树状数组适用于矩阵单点修改、子矩阵和的场景，复杂度为O(log n * log m)。

8. 常见问题与排查思路

树状数组代码虽短，但初学者容易踩坑。下面整理高频问题：

8.1 排查思路

如果某个测试数据不通过，建议按下面顺序排查：

1. 检查下标是否从 1 开始，尤其注意输入数组下标转换。
2. 手动模拟一个长度在 5 以内的小样例，逐步打印t[]数组的变化。
3. 区分n的含义：是数组长度还是最大下标，是否在程序开头初始化。
4. 检查所有累加变量是否使用long long。
5. 如果有取模操作，确认每一步取模的时机，避免减出负数。
6. 如果是离散化，打印映射后的rank数组，确认每个原位置都映射到了正确排名。

9. 工程建议与易错点

9.1 通用代码规范

• lowbit函数建议写成inline，减少函数调用开销。
• 树状数组大小固定为n + 1，不要写成n，否则最后一下更新可能越界。
• 全局变量默认初始化为 0，不需要重复 memset。如果使用局部数组，记得初始化。
• 多组输入时，如果树状数组大小不同，需要重新初始化，通常用fill(t, t + n + 1, 0)而不是memset全部清空，节约时间。

9.2 性能优化建议

• 关闭 C++ 的输入输出同步，使用ios::sync_with_stdio(false)和cin.tie(0)，或者直接用scanf/printf。
• 在update和query频繁调用的场景下，函数内避免额外判断和多余的递归。
• 能用树状数组就不建议用线段树，动态维护前缀和的场景树状数组常数更小。

9.3 学习路径建议

树状数组的进阶路线可以这样规划：

1. 掌握lowbit和基本单点修改、区间查询模板。
2. 理解差分思想，掌握区间修改 + 区间查询。
3. 练习逆序对和离散化。
4. 掌握树状数组上二分。
5. 扩展到二维树状数组、离线查询。
6. 学会把树状数组与数学推导、计数问题结合。

每一步都可以在在线评测平台上找对应模板题练习，边做题边总结，比只读文章有效得多。

10. 总结

树状数组是算法竞赛中性价比最高的数据结构之一。它代码量少、运行速度快、思路清晰，能解决一大类动态前缀和与区间统计问题。核心就是理解lowbit运算和二进制分解思想，再把单点修改、前缀和查询两个基本操作练熟。

本文从基本原理开始，讲解了树状数组的存储结构、基本操作、区间修改的实现方式，并给出了逆序对、树状数组上二分等高阶应用。如果你正在备赛或复习数据结构，建议把每段代码都亲手敲一遍，改一改参数，观察输出变化。代码只有自己写一遍，才能真正理解其中的二进制跳跃逻辑。

如果这篇文章对你有帮助，可以收藏备用，方便刷题时快速查阅模板。也欢迎在评论区交流你在树状数组使用中遇到的奇怪问题，一起讨论排错思路。