GESP 8级 · 树状数组（Fenwick Tree）

📖概念讲解

树状数组（Binary Indexed Tree / Fenwick Tree）是一种支持单点修改和前缀和查询的数据结构，两个操作都是 O(log n)。它比线段树代码短得多，常用来处理「频繁更新 + 频繁查询前缀和」的场景。

核心思想：利用二进制的 lowbit（最低位的1）把数组组织成一棵"树"。每个节点管辖一段区间的和，通过不断跳 parent 可以快速求前缀和。

lowbit(x) = x & (-x)：取出 x 二进制最低位的 1，是整个结构的灵魂
add(i, v)：单点加，沿着树往上更新所有管辖区间包含 i 的节点
query(i)：求前缀和 a[1]+...+a[i]，沿着树往下跳，累加各段

💻代码示例

#include<iostream>
using namespace std;
int n, tree[100005]; // tree[] 为树状数组，下标从1开始
// lowbit：取最低位的1，如 lowbit(6)=lowbit(110₂)=2
int lowbit(int x) { return x & (-x); }
// 单点修改：a[i] 加上 val
void add(int i, int val) {
    while (i <= n) {       // 往上跳，更新所有管辖区间包含 i 的节点
        tree[i] += val;     // 当前节点累加 val
        i += lowbit(i);     // 跳到 parent 节点
    }
}
// 前缀和查询：求 a[1]+a[2]+...+a[i]
int query(int i) {
    int sum = 0;
    while (i > 0) {        // 往下跳，累加各段
        sum += tree[i];      // 累加当前节点管辖的区间和
        i -= lowbit(i);      // 跳到下一个更小的区间
    }
    return sum;
}
int main() {
    n = 5;
    int a[] = {0, 3, 1, 4, 1, 5}; // 原始数组，下标从1开始
    for (int i = 1; i <= n; i++) add(i, a[i]); // 逐个插入建树
    cout << "前缀和[1..3]: " << query(3) << endl; // 3+1+4=8
    add(3, 2);             // a[3] 从4变成6
    cout << "修改后[1..3]: " << query(3) << endl; // 3+1+6=10
    cout << "前缀和[1..5]: " << query(5) << endl; // 3+1+6+1+5=16
}
// 输出: 前缀和[1..3]: 8  修改后[1..3]: 10  前缀和[1..5]: 16

🧩互动小测

Q1: lowbit(12) 的值是？

Q2: 树状数组 query(5) 会累加哪些 tree[] 节点？

Q3: 单点修改 add(i, v) 的时间复杂度是？

🏋️动手练一练

📝 编程练习

给定一个长度为 n 的数组，支持两种操作：
1. add(i, v)：将第 i 个元素增加 v
2. sum(l, r)：查询区间 [l, r] 的和

提示：区间和 = query(r) - query(l-1)。用树状数组实现这两个操作。

参考答案：

#include <iostream>
using namespace std;
int n, tree[100005];
int lowbit(int x) { return x & (-x); }
void add(int i, int v) { while (i <= n) { tree[i] += v; i += lowbit(i); } }
int query(int i) { int s = 0; while (i > 0) { s += tree[i]; i -= lowbit(i); } return s; }
int main() {
    n = 5; int a[] = {0, 3, 1, 4, 1, 5};
    for (int i = 1; i <= n; i++) add(i, a[i]);
    cout << query(3) - query(0) << endl;  // sum(1,3) = 8
    add(2, 10);                           // a[2] += 10
    cout << query(5) - query(2) << endl;  // sum(3,5) = 4+1+5=10
}

要点：区间和 = query(r) - query(l-1)，这是树状数组的常用技巧。注意 query(0) 返回 0，不用特判。

📝易错点提醒

下标从 1 开始：树状数组习惯用 1-indexed，和 0-indexed 的原数组要做转换（a[i] 对应 tree[i+1]）
lowbit 是 x & (-x)，不是 x & ~(x-1)，虽然结果一样但前者更常用。注意负数的补码表示
add 和 query 的循环方向相反：add 往上跳（i += lowbit(i)），query 往下跳（i -= lowbit(i)），别搞反
区间和用差分：求 [l, r] 区间和要算 query(r) - query(l-1)，而不是 query(r) - query(l)
树状数组 vs 线段树：树状数组只能做前缀和类操作（单点修改+区间查询），线段树更通用但代码更长

📘树状数组（Fenwick Tree）