C++怎么实现一个二进制索引树(BIT)_C++数据结构与Fenwick树的高效实现-C++-PHP中文网

C++怎么实现一个二进制索引树(BIT)_C++数据结构与Fenwick树的高效实现

下次还敢

发布： 2025-11-23 19:43:02

原创

743人浏览过

二进制索引树（Fenwick树）通过lowbit操作实现O(log n)单点更新和前缀和查询，基于1-indexed数组，支持高效动态前缀和计算与区间和查询，适用于频繁更新与求和场景，代码简洁且性能优越。

c++怎么实现一个二进制索引树(bit)_c++数据结构与fenwick树的高效实现

二进制索引树（Binary Indexed Tree, BIT），也叫 Fenwick 树，是一种高效处理动态前缀和查询与单点更新的数据结构。它支持在 O(log n) 时间内完成单点修改和前缀和查询，实现简洁且常数小，特别适合频繁更新与查询的场景。

BIT 的基本原理

BIT 利用整数的二进制表示特性来组织数据。每个节点 tree[i] 存储从某个位置开始、长度为 i & (-i)（即 lowbit）的区间和。

关键操作是 lowbit(x)，用于提取 x 的最低位 1 所代表的值：

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

登录后复制

例如：lowbit(6) = lowbit(110₂) = 10₂ = 2。

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

树的构建与操作实现

BIT 通常基于 1-indexed 数组实现，便于计算父节点与子节点关系。

1. 单点更新

将位置 i 的值增加 delta，并更新所有覆盖该位置的节点：

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

登录后复制

2. 前缀和查询

计算从 1 到 i 的前缀和：

必应图像创建器

微软必应出品的AI绘图工具

593

查看详情

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

登录后复制

3. 区间查询

区间 [l, r] 的和可通过前缀和相减得到：

int range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

登录后复制

C++ 完整实现示例

下面是一个完整的 BIT 类封装：

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

登录后复制

public: FenwickTree(int size) { n = size; tree.assign(n + 1, 0); }

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

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

int range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

登录后复制

};

// 使用示例 int main() { FenwickTree bit(5); bit.update(1, 10); bit.update(2, 20); bit.update(3, 30);

cout << "Sum [1,3]: " << bit.range_sum(1, 3) << endl; // 输出 60
cout << "Sum [2,4]: " << bit.range_sum(2, 4) << endl; // 输出 50

bit.update(2, 10); // 更新位置2 +10
cout << "Sum [1,3]: " << bit.range_sum(1, 3) << endl; // 输出 70

return 0;

登录后复制

}