C++怎么实现一个树状数组_C++高效实现单点修改与区间求和的Fenwick树-C++-PHP中文网

C++怎么实现一个树状数组_C++高效实现单点修改与区间求和的Fenwick树

穿越時空

发布： 2025-11-28 15:11:03

原创

187人浏览过

树状数组通过lowbit实现高效单点更新和区间求和，支持O(log n)操作，适用于动态前缀和场景。

c++怎么实现一个树状数组_c++高效实现单点修改与区间求和的fenwick树

树状数组（Fenwick Tree）是一种高效处理单点更新和区间求和的数据结构，代码简洁、常数小，特别适合在频繁修改与查询的场景中使用。C++ 实现 Fenwick 树非常直观，下面介绍其核心原理与实现方式。

树状数组的基本思想

Fenwick 树利用二进制特性维护前缀和。每个节点存储一段区间的和，通过 lowbit 操作快速定位父节点或子节点。支持：

单点修改：更新某个位置的值，影响 O(log n) 个节点
前缀查询：求 [1, i] 的和，访问 O(log n) 个节点
结合前缀和可得任意区间 [l, r] 的和

lowbit 函数的实现

lowbit(x) 返回 x 的二进制表示中最低位 1 所对应的值，例如 lowbit(6)=2（6=110₂）。C++ 中可通过位运算高效实现：

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

登录后复制

树状数组的封装实现

以下是一个完整的 C++ 类封装，支持单点加法和区间求和：

立即学习“C++免费学习笔记（深入）”；

#include <vector>
<p>class FenwickTree {
private:
std::vector<long long> tree;
int n;</p><pre class='brush:php;toolbar:false;'>int lowbit(int x) {
    return x & (-x);
}

登录后复制

public: // 构造函数，n 为原数组长度 FenwickTree(int size) { n = size; tree.assign(n + 1, 0); }

// 单点增加：在位置 i 上加上 delta（i 从 1 开始）
void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

// 前缀求和：[1, i] 的和
long long prefixSum(int i) {
    long long sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

// 区间求和：[l, r] 的和（l 和 r 都从 1 开始）
long long rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

登录后复制

};

腾讯交互翻译

腾讯AI Lab发布的一款AI辅助翻译产品

183

查看详情

使用示例与注意事项

假设有一个初始数组 [1, 3, 5, 7, 9]，我们可以这样使用 FenwickTree：

#include <iostream>
using namespace std;
<p>int main() {
FenwickTree fw(5);</p><pre class='brush:php;toolbar:false;'>// 模拟初始化：逐个添加元素
fw.update(1, 1);
fw.update(2, 3);
fw.update(3, 5);
fw.update(4, 7);
fw.update(5, 9);

cout << "Sum [1,3]: " << fw.rangeSum(1, 3) << endl; // 输出 9
fw.update(2, 2); // A[2] += 2
cout << "Sum [1,3] after update: " << fw.rangeSum(1, 3) << endl; // 输出 11

return 0;

登录后复制

}

注意：FenwickTree 通常基于 1 索引设计，传入的下标应从 1 开始。若原始数据是 0 索引，使用时需 +1 映射。

基本上就这些。实现简单，效率高，适合竞赛和工程中需要动态前缀和的场合。

以上就是C++怎么实现一个树状数组_C++高效实现单点修改与区间求和的Fenwick树的详细内容，更多请关注php中文网其它相关文章！