二进制索引树（Fenwick树）通过lowbit操作实现O(log n)单点更新和前缀和查询，基于1-indexed数组，支持高效动态前缀和计算与区间和查询，适用于频繁更新与求和场景，代码简洁且性能优越。
二进制索引树（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 的前缀和：
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 #include using namespace std;class FenwickTree {private:vector tree;int n;
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 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; // 输出 60cout << "Sum [2,4]: " << bit.range_sum(2, 4) << endl; // 输出 50bit.update(2, 10); // 更新位置2 +10cout << "Sum [1,3]: " << bit.range_sum(1, 3) << endl; // 输出 70return 0;
}
应用场景与优势
BIT 适用于以下场景：
动态数组的频繁前缀和查询逆序对计数（配合离散化）一维或多维差分更新与查询替代线段树在简单需求下的使用，代码更短，效率更高
相比线段树，BIT 实现更简单，内存占用更少，常数更小。虽然功能稍有限，但在只涉及单点更新+前缀查询时是首选。
基本上就这些。掌握 lowbit、update 和 prefix_sum 三个核心，就能灵活运用 BIT 解决很多问题。
以上就是C++怎么实现一个二进制索引树(BIT)_C++数据结构与Fenwick树的高效实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485730.html
微信扫一扫 
支付宝扫一扫 
