🌳 树状数组（Fenwick Tree）：一次真正讲明白的入门指南

在算法竞赛、OI 以及日常数据结构学习中，我们经常遇到这样的问题：

  • 有一个数组

  • 需要频繁修改某个位置的值

  • 同时还要频繁查询某一段区间的和

如果每次修改或查询都暴力遍历数组，时间复杂度是 O(n)，数据规模稍微大一点就会直接超时。

这正是 树状数组（Fenwick Tree） 的用武之地。

一、树状数组是什么？一句话理解

树状数组是一种支持 O(log n) 单点修改和前缀和查询的数据结构。

它的特点非常鲜明：

  • 基于数组实现，不是真正的“树”

  • 利用二进制的性质进行区间划分

  • 实现简单、常数小

  • 非常适合做“加法型”问题

二、为什么叫“树状数组”？

虽然代码中只有一个数组 c[]，
但在逻辑上，每个下标都代表了一个区间的和，这些区间之间构成了一棵“隐式的树”。

以 n = 8 为例：

1
下标:   1  2  3  4  5  6  7  8

每个位置维护的区间是：

1
2
3
4
5
6
7
8
c[1] -> [1,1]
c[2] -> [1,2]
c[3] -> [3,3]
c[4] -> [1,4]
c[5] -> [5,5]
c[6] -> [5,6]
c[7] -> [7,7]
c[8] -> [1,8]

如果画成一棵逻辑树，大致是这样：

1
2
3
4
             [1,8]
       [1,4]         [5,8]
  [1,2]    [3,4]  [5,6]  [7,8]
[1] [2]  [3] [4] [5] [6] [7] [8]

关键理解点：

树状数组中，每个节点存的不是单个值，而是一段区间的和。

三、lowbit：树状数组的核心

树状数组的灵魂只有一句代码：

1
lowbit(x) = x & (-x)

它的作用是：

提取 x 的二进制表示中，最低位的 1 所对应的值

举几个直观的例子：

x 二进制 lowbit(x)
8 1000 8
6 0110 2
7 0111 1
12 1100 4

lowbit 的意义

  • 决定当前节点所维护的区间长度

  • 决定查询和更新时“该跳到哪里”

一句话记忆：

lowbit 决定了当前节点能“管多大一段区间”

四、树状数组的两种基本操作

1️⃣ 单点修改（add）

假设要执行操作：

1
a[x] += v

在树状数组中，我们需要更新所有包含位置 x 的区间节点。

代码如下：

1
2
3
4
5
6
void add(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}

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

因为：

  • c[x] 管理的是一个区间

  • 它的父节点管理更大的区间

  • 父节点的下标正好是 x + lowbit(x)

2️⃣ 前缀和查询（sum）

查询 [1, x] 的区间和：

1
2
3
4
5
6
7
8
int sum(int x) {
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

这个过程可以理解为：

  • 每次取一个最大的、不重叠的区间

  • 然后向前跳

  • 直到回到 0

例如查询 sum(7)：

1
7 -> 6 -> 4 -> 0

五、区间和如何实现？

虽然树状数组只能直接求前缀和，但区间和非常容易转化：

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

这是树状数组最常见、也是最重要的用法之一。

六、完整 C++ 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n;
int c[N];

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

void add(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}

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

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

七、什么时候该用树状数组？

非常适合以下场景：

  • 单点修改 + 区间求和

  • 动态前缀统计

  • 逆序对计数

  • 离散化后做频率统计

如果涉及：

  • 区间修改

  • 区间最值

那就应该考虑线段树或其他结构了。

八、总结

树状数组 = 二进制思想 + 前缀和优化 + 极简实现

刚开始接触时可能会觉得抽象，但只要真正理解了 lowbit 和“区间跳跃”的思想，
树状数组会成为你算法工具箱中使用频率极高的一种数据结构。