一、概述
树状数组（Fenwick Tree / Binary Indexed Tree，简称 BIT），是由 Peter M. Fenwick 于 1994 年提出的一种用于维护数列前缀和与差分的数据结构。它以其简洁的实现、优秀的常数性能和极低的空间开销，在算法竞赛和工程实践中广为应用。
树状数组的核心特征：
- 支持 单点更新（将某个元素增加一个值）和 前缀和查询（求前 k 个元素的和），两种操作的时间复杂度均为 O(log n)
- 空间复杂度为 O(n)，仅需一个长度为 n+1 的数组
- 代码实现极为简洁——核心操作仅需几行代码
- 通过差分技巧可扩展为 区间更新 + 单点查询 和 区间更新 + 区间查询
- 可以推广到二维及多维，用于处理矩阵中的子矩阵求和问题
树状数组本质上是对原始数组的一种 树形映射。它将长度为 n 的序列映射到一个树形结构中，每个节点负责维护一段连续区间的信息。具体来说，对于下标 i，树状数组的节点 tree[i] 维护了原始数组中区间 [i - lowbit(i) + 1, i] 的和。lowbit 是这一切的起点。
二、核心思想：lowbit 与二进制表示
lowbit 函数
lowbit(x) 定义为 x 的二进制表示中最低位的 1 及其后所有 0 所构成的数值。例如：
- lowbit(6)：6 的二进制为 110，最低位 1 在第二位，所以 lowbit(6) = 2
- lowbit(8)：8 的二进制为 1000，最低位 1 在第四位，所以 lowbit(8) = 8
- lowbit(7)：7 的二进制为 111，最低位 1 在第一位，所以 lowbit(7) = 1
计算 lowbit 有一个经典技巧：lowbit(x) = x & (-x)。这是因为在计算机的补码表示中，-x 等于 ~x + 1，两者按位与恰好得到最低位的 1。
树状数组对下标从 1 开始编号（避开下标 0 简化 lowbit 运算）。对于任意下标 i，节点 tree[i] 存储的是原数组 a[i - lowbit(i) + 1] 到 a[i] 这 lowbit(i) 个元素的和。下图展示了下标 1 到 16 的管辖范围：
- 下标 1（二进制 1）：lowbit(1)=1，管辖 [1, 1]
- 下标 2（二进制 10）：lowbit(2)=2，管辖 [1, 2]
- 下标 3（二进制 11）：lowbit(3)=1，管辖 [3, 3]
- 下标 4（二进制 100）：lowbit(4)=4，管辖 [1, 4]
- 下标 6（二进制 110）：lowbit(6)=2，管辖 [5, 6]
- 下标 8（二进制 1000）：lowbit(8)=8，管辖 [1, 8]
树状数组的树形结构就是由这些管辖关系构成的。对于每个节点 i，它的 父节点 是 i + lowbit(i)，它的 前驱节点（前缀和查找路径上的下一个节点）是 i - lowbit(i)。这正是树状数组两种核心操作的基础。
// 计算 lowbit
int lowbit(int x) {
return x & -x;
}
lowbit 函数的 C++ 实现
三、核心操作
3.1 单点更新：add
将原数组中下标为 i 的元素增加 val。由于 tree[i] 管辖了包含 i 在内的若干区间，我们需要更新所有包含 i 的节点。从 i 开始，不断沿父链 i += lowbit(i) 向上更新直到 n。
// 单点更新：将 a[idx] 增加 val
void add(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
树状数组单点更新操作
3.2 前缀和查询：query
查询原数组前 idx 个元素的和（即 a[1] + a[2] + ... + a[idx]）。从 idx 开始，不断沿前驱链 idx -= lowbit(idx) 累加直到 idx 为 0。
// 前缀和查询：返回前 idx 个元素的和
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
树状数组前缀和查询操作
3.3 区间和查询
查询区间 [l, r] 的和，利用前缀和相减即可得到：
// 区间和查询：返回 [l, r] 的和
int range_query(int l, int r) {
return query(r) - query(l - 1);
}
区间和查询利用前缀和性质
操作时间复杂度分析
- add 操作：每个循环移除 lowbit(i) 个最低位的 1，相当于二进制位从低到高遍历，最多执行 log₂n 次
- query 操作：同样每个循环移除 lowbit(i)，最多执行 log₂n 次
- 常数极小：每次循环仅包含一次加法/减法 + 一次位运算 + 一次赋值，比线段树快许多
四、建树方法
4.1 朴素方法：O(n log n)
初始化树状数组全部为 0，然后对每个位置 i 调用 add(i, a[i])。这是最直观的建树方式，代码简单，但时间复杂度为 O(n log n)。
// 朴素建树：O(n log n)
int tree[MAXN];
int n, a[MAXN];
void build_naive() {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= n; i++) {
add(i, a[i]);
}
}
朴素建树，对每个元素调用 add
4.2 线性建树：O(n)
利用树状数组的性质，可以在 O(n) 时间内完成建树。节点 tree[i] 管辖 [i - lowbit(i) + 1, i] 的和，我们可以先计算原数组的前缀和 pre[i]，然后直接赋值 tree[i] = pre[i] - pre[i - lowbit(i)]。
// 线性建树：O(n)
void build_linear() {
// 方法一：利用前缀和
int pre[MAXN];
pre[0] = 0;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
tree[i] = pre[i] - pre[i - lowbit(i)];
}
// 方法二：更简洁的 O(n) 建树（推荐）
// 利用父节点累加：tree[i] 先将 a[i] 加给自己，
// 然后如果 i + lowbit(i) <= n，将 tree[i] 累加到父节点
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= n; i++) {
tree[i] += a[i];
int j = i + lowbit(i);
if (j <= n) {
tree[j] += tree[i];
}
}
}
O(n) 线性建树的两种实现
五、扩展应用
5.1 区间更新 + 单点查询
将原数组 a 转化为其 差分数组 d，其中 d[i] = a[i] - a[i - 1]（约定 a[0] = 0）。
- 对原数组的区间 [l, r] 整体增加 val，等价于 add(l, val) 和 add(r + 1, -val)
- 查询原数组的 a[i]，等价于对差分数组求前缀和 query(i)
// 区间更新 + 单点查询（基于差分）
// 对 [l, r] 每个元素增加 val
void range_add(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
// 查询 a[idx] 的值
int point_query(int idx) {
return query(idx);
}
基于差分的区间更新单点查询
5.2 区间更新 + 区间查询
这是树状数组最有价值的扩展之一。需要维护两个树状数组来实现区间更新 + 区间求和。推导如下：
设原数组为 a，差分数组为 d[i] = a[i] - a[i - 1]，则：
a[1] + a[2] + ... + a[n] = n * d[1] + (n - 1) * d[2] + ... + 1 * d[n]
= (n + 1) * (d[1] + d[2] + ... + d[n]) - (1 * d[1] + 2 * d[2] + ... + n * d[n])
因此我们需要维护两个树状数组：
- tree1：维护差分 d[i]
- tree2：维护 i * d[i]
// 区间更新 + 区间查询
int tree1[MAXN], tree2[MAXN];
void add(int tree[], int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
int sum(const int tree[], int idx) {
int res = 0;
while (idx > 0) {
res += tree[idx];
idx -= lowbit(idx);
}
return res;
}
// 区间 [l, r] 增加 val
void range_add(int l, int r, int val) {
add(tree1, l, val);
add(tree1, r + 1, -val);
add(tree2, l, l * val);
add(tree2, r + 1, -(r + 1) * val);
}
// 前缀和查询：a[1] + ... + a[idx]
int prefix_sum(int idx) {
return (idx + 1) * sum(tree1, idx) - sum(tree2, idx);
}
// 区间和查询：a[l] + ... + a[r]
int range_sum(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
双树状数组实现区间更新 + 区间查询
5.3 二维树状数组
将树状数组推广到二维。二维 BIT 用于处理矩阵上的子矩阵求和与单点更新问题。其思想是将一维 BIT 嵌套使用：外层遍历 x 坐标，内层遍历 y 坐标。
// 二维树状数组（单点更新 + 子矩阵查询）
int bit[MAXN][MAXN];
int n, m; // 矩阵维度
int lowbit(int x) {
return x & -x;
}
void add(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;
}
}
}
// 查询从 (1,1) 到 (x,y) 的子矩阵和
int sum(int x, int y) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
res += bit[i][j];
}
}
return res;
}
// 查询 (x1,y1) 到 (x2,y2) 的子矩阵和（容斥原理）
int range_sum(int x1, int y1, int x2, int y2) {
return sum(x2, y2) - sum(x1 - 1, y2)
- sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
}
二维树状数组实现，注意容斥原理的应用
二维 BIT 的时间复杂度为 O(log n * log m)，空间复杂度为 O(n * m)。它同样支持通过差分实现子矩阵更新 + 子矩阵查询，但需要维护 4 个二维 BIT。
六、树状数组与线段树对比
树状数组和线段树都是用于处理区间查询问题的树形数据结构，但各有优劣。下表从多个维度进行对比：
| 对比维度 |
树状数组 (BIT) |
线段树 (Segment Tree) |
| 代码长度 |
极短（核心操作各 3-5 行） |
较长（建树、更新、查询各约 10-15 行） |
| 常数因子 |
极小（循环+位运算） |
较大（递归/函数调用开销） |
| 空间占用 |
O(n)，精确 n+1 |
O(4n) 或 O(2n) |
| 区间查询 |
前缀和性质，可求区间和 |
支持任意区间操作（和、最值、GCD等） |
| 区间更新 |
通过差分或双 BIT 实现 |
原生支持（配合懒标记 Lazy Propagation） |
| 区间最值 |
不支持（无法处理不可减信息） |
原生支持（RMQ 问题） |
| 动态开点 |
不支持（需要固定大小） |
支持（动态线段树/主席树） |
| 可持久化 |
较难实现 |
支持（主席树/可持久化线段树） |
| 维度扩展 |
自然支持二维及多维 |
高维复杂度过高 |
选型建议
- 优先选择树状数组：当问题仅涉及区间求和/差分、无需区间最值、数据规模固定且不需要可持久化时
- 必须使用线段树：当需要区间最值、区间 GCD、需要懒标记进行区间修改、需要可持久化或动态开点时
- 两者皆可：对于基本的区间更新 + 区间求和问题，从代码量和性能角度建议优先使用树状数组
- 很多竞赛选手会同时掌握两种数据结构，并且在比赛中根据具体问题选择最合适的工具
七、逆序对计算
逆序对（Inversion Pair）是算法竞赛中的经典问题。给定一个序列，如果 i < j 且 a[i] > a[j]，则称 (i, j) 为一个逆序对。树状数组可以在 O(n log n) 时间内高效计算逆序对数量。
算法思路
- 离散化：如果原始数据范围很大（如 10⁹），先进行离散化，将值映射到 [1, n] 的范围内
- 倒序扫描：从右向左遍历数组，对于每个元素 a[i]，查询树状数组中小于 a[i] 的元素个数（即已出现过且值更小的元素数量），累加到答案中
- 更新计数：在树状数组中将 a[i] 对应的位置 +1，标记该值已出现
// 使用树状数组计算逆序对
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int tree[MAXN], n;
int lowbit(int x) {
return x & -x;
}
void add(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
// 计算逆序对
long long count_inversions(vector<int>& arr) {
// 1. 离散化
vector<int> sorted(arr);
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (int &x : arr) {
x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
}
// 2. 倒序扫描 + 树状数组统计
n = sorted.size();
memset(tree, 0, sizeof(tree));
long long ans = 0;
for (int i = arr.size() - 1; i >= 0; i--) {
ans += query(arr[i] - 1); // 统计比 arr[i] 小的已出现元素
add(arr[i], 1); // 将 arr[i] 标记为已出现
}
return ans;
}
树状数组计算逆序对（含离散化）
树状数组求解逆序对的核心思想是"边扫描边统计"——利用树状数组动态维护已遍历元素中各值的出现次数，每次查询小于当前值的元素个数并累加，优雅地将暴力 O(n²) 优化为 O(n log n)。
八、典型例题与模板
例题1：LeetCode 307. Range Sum Query - Mutable
给定一个整数数组 nums，支持两种操作：更新某个元素的值；查询区间 [l, r] 的和。这是树状数组最直接的模板题。
// LeetCode 307 - 树状数组解法
class NumArray {
private:
vector<int> tree;
vector<int> nums;
int n;
int lowbit(int x) {
return x & -x;
}
void add(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
public:
NumArray(vector<int>& nums) : nums(nums) {
n = nums.size();
tree.resize(n + 1, 0);
for (int i = 0; i < n; i++) {
add(i + 1, nums[i]);
}
}
void update(int index, int val) {
int delta = val - nums[index];
nums[index] = val;
add(index + 1, delta);
}
int sumRange(int left, int right) {
return query(right + 1) - query(left);
}
};
LeetCode 307 树状数组实现
例题2：LeetCode 315. Count of Smaller Numbers After Self
给定一个整数数组 nums，返回一个新数组 counts，其中 counts[i] 表示 nums[i] 右侧比它小的元素个数。这正是逆序对问题的一个变种，区别在于需要输出每个位置对应的逆序数而非总数。
// LeetCode 315 - 树状数组解法
class Solution {
private:
int lowbit(int x) { return x & -x; }
void add(vector<int>& tree, int idx, int val, int n) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
int query(vector<int>& tree, int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
public:
vector<int> countSmaller(vector<int>& nums) {
// 离散化
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int n = sorted.size();
vector<int> tree(n + 1, 0);
vector<int> result(nums.size());
// 从右向左遍历
for (int i = nums.size() - 1; i >= 0; i--) {
int idx = lower_bound(sorted.begin(), sorted.end(), nums[i])
- sorted.begin() + 1;
result[i] = query(tree, idx - 1);
add(tree, idx, 1, n);
}
return result;
}
};
LeetCode 315 树状数组解法（右侧小于当前元素个数）
例题3：区间调度与区间覆盖统计
给定若干区间 [l, r]，统计每个点被多少个区间覆盖。这是一个典型的区间更新 + 单点查询问题，使用树状数组加差分即可高效解决。
// 区间覆盖统计：差分 + 树状数组
const int MAX_POS = 1000000;
int bit[MAX_POS + 2];
void add_interval(int l, int r) {
add(l, 1); // 从 l 开始区间覆盖 +1
add(r + 1, -1); // 从 r+1 开始覆盖恢复
}
int query_point(int x) {
return query(x); // 返回 x 被多少个区间覆盖
}
使用差分树状数组统计区间覆盖次数
九、树状数组的实现细节与优化
9.1 下标从 1 开始
树状数组的下标必须从 1 开始，因为 lowbit(0) = 0 会导致死循环。在实际编码时，需要对原始输入的下标进行 +1 偏移。
9.2 使用 vector<int> 替代定长数组
在 C++ 中，建议使用 vector<int> bit(n + 1) 来动态创建树状数组，避免静态分配的固定大小限制。
9.3 模板化（支持不同数据类型）
// 树状数组模板类
template <typename T>
class Fenwick {
private:
int n;
vector<T> tree;
public:
Fenwick(int size) : n(size), tree(size + 1, T()) {}
void add(int idx, T val) {
while (idx <= n) {
tree[idx] += val;
idx += idx & -idx;
}
}
T sum(int idx) {
T res = T();
while (idx > 0) {
res += tree[idx];
idx -= idx & -idx;
}
return res;
}
T range_sum(int l, int r) {
return sum(r) - sum(l - 1);
}
};
泛型树状数组模板类，支持不同类型（int, long long, double 等）
9.4 找到第 k 个前缀和
树状数组支持在 O(log n) 时间内找到最小的前缀和大于等于 k 的位置（即二分查找树状数组上的前缀和）。这在求中位数、订单统计等问题中非常有用。
// 查找最小的 idx，使得 sum(idx) >= k（树状数组上二分）
// 前提：所有值非负
int find_kth(int k) {
int idx = 0;
// 从最高位开始逼近
for (int bit = 1 << 20; bit > 0; bit >>= 1) {
int next = idx + bit;
if (next <= n && tree[next] < k) {
k -= tree[next];
idx = next;
}
}
return idx + 1; // 对应原数组的下标
}
树状数组上的二分查找（求第 k 大的元素）
十、核心要点总结
- 本质：树状数组利用二进制表示（lowbit）维护前缀和，每个节点 tree[i] 管辖区间 [i - lowbit(i) + 1, i]
- 单点更新：沿父链 i += lowbit(i) 向上走，更新所有包含该位置的节点
- 前缀和查询：沿前驱链 i -= lowbit(i) 向下走，累加所经节点的值
- 差分扩展：通过差分数组实现区间更新 + 单点查询；通过双 BIT 实现区间更新 + 区间查询
- 二维扩展：嵌套遍历 x 和 y 维度，支持子矩阵求和，时间复杂度 O(log n * log m)
- 逆序对：离散化 + 倒序扫描 + BIT 维护频次，O(n log n) 解决经典问题
- 与线段树对比：BIT 代码更短、常数更小、空间更省，但功能不如线段树丰富（不支持区间最值、懒标记、可持久化）
- 适用场景：求前缀和 / 区间和、求逆序对、维护差分、求第 k 大的前缀和、二维子矩阵求和
十一、进一步思考
实战应用场景
树状数组虽然看起来只是算法竞赛中的数据结构，但其背后的 单点贡献累积 思想在工程领域有广泛应用：
- 频率统计：统计流式数据中各值的出现频次、实时 Top-K 查询
- 股票交易量：维护不同价格区间的累计交易量，查询某个区间的总交易额
- 在线广告计数：实时统计广告展示次数、点击次数的区间汇总
- 游戏排行榜：使用树状数组维护玩家分数分布，快速查询排名
- 数据库基数估计：近似统计不同值数量时，树状数组可辅助维护前缀频次
扩展学习路线
- 区间最值：学习线段树（Segment Tree）以处理 RMQ 问题
- 可持久化：掌握主席树（可持久化线段树）以实现历史版本查询
- 树链剖分：将树状数组与树链剖分结合，处理树上路径求和问题
- 多维 BIT：掌握三维及以上 BIT 的原理（高维 BIT 空间开销大需谨慎）
- Fenwick Tree 变种：研究 Range BIT（支持区间加 + 区间查询的另一种实现）