C++树状数组详解（从零开始掌握高效前缀和操作）

核心思想：lowbit 函数

树状数组的关键在于 lowbit(x) 函数，它返回 x 的二进制表示中最低位的 1 所对应的值。例如：
- lowbit(6) = lowbit(110₂) = 10₂ = 2
- lowbit(8) = lowbit(1000₂) = 1000₂ = 8

在 C++ 中，lowbit 可以用位运算高效实现：

inline int lowbit(int x) {    // 利用补码特性：x & (-x)    return x & (-x);}

树状数组的基本操作

树状数组主要支持两种操作：
1. 单点更新（update）：在某个位置加上一个值。
2. 前缀和查询（query）：查询从第 1 个元素到第 i 个元素的和。

1. 前缀和查询（query）

查询前缀和时，我们从索引 i 开始，不断减去 lowbit(i)，累加对应 tree 值，直到 i 变为 0。

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

2. 单点更新（update）

更新时，从索引 i 开始，不断加上 lowbit(i)，将增量加到所有受影响的 tree 节点上。

void update(int i, int delta) {    while (i <= n) { // n 是数组长度        tree[i] += delta;        i += lowbit(i);    }}

完整 C++ 实现示例

下面是一个完整的 树状数组实现 示例，包含初始化、更新和查询功能：

#include <iostream>#include <vector>using namespace std;class FenwickTree {private:    vector<int> tree;    int n;public:    FenwickTree(int size) {        n = size;        tree.assign(n + 1, 0); // 索引从1开始，所以大小为n+1    }    inline int lowbit(int x) {        return x & (-x);    }    // 更新位置i（1-based），增加delta    void update(int i, int delta) {        while (i <= n) {            tree[i] += delta;            i += lowbit(i);        }    }    // 查询前缀和 [1, i]    int query(int i) {        int sum = 0;        while (i > 0) {            sum += tree[i];            i -= lowbit(i);        }        return sum;    }    // 查询区间 [l, r] 的和    int rangeQuery(int l, int r) {        return query(r) - query(l - 1);    }};// 使用示例int main() {    int arr[] = {1, 3, 5, 7, 9, 11};    int n = sizeof(arr) / sizeof(arr[0]);    FenwickTree ft(n);    // 初始化树状数组    for (int i = 0; i < n; ++i) {        ft.update(i + 1, arr[i]); // 注意：树状数组使用1-based索引    }    cout << "前缀和 [1, 3]: " << ft.query(3) << endl; // 输出 1+3+5=9    cout << "区间和 [2, 5]: " << ft.rangeQuery(2, 5) << endl; // 输出 3+5+7+9=24    // 更新位置3，加2    ft.update(3, 2);    cout << "更新后前缀和 [1, 3]: " << ft.query(3) << endl; // 输出 11    return 0;}

为什么选择树状数组？

相比于线段树，树状数组代码更简洁、常数更小、更容易调试。虽然功能不如线段树强大（例如不支持任意区间更新），但在处理单点更新 + 区间查询这类问题时，它是首选的数据结构之一。这也是为什么在算法竞赛中，数据结构C++学习者必须掌握它。

总结

通过本教程，你已经学会了：
✅ 树状数组的核心思想（lowbit）
✅ 如何实现查询和更新操作
✅ 完整的 C++ 类封装示例
✅ 树状数组的适用场景

掌握了这些，你就具备了使用 C++树状数组 解决实际问题的能力！建议多做练习，比如在 LeetCode 或 Codeforces 上找相关题目巩固知识。

关键词回顾：C++树状数组、树状数组实现、树状数组教程、数据结构C++