1. Fenwick树的基本原理与数据结构
原理概述
在众多数据结构中，二进制索引树（BIT，Fenwick Tree）以一维数组为底层存储，通过对下标的位运算来实现快速的前缀和查询与单点更新。核心思想是将数组的前缀和分解为若干个区间的贡献，每次更新影响到若干个区间的和，查询则通过累加这些区间的贡献得到前缀和。
通过实现一个1-based的下标体系，我们可以使用idx += idx & -idx来跳跃到下一个相关区间，并用idx -= idx & -idx来沿着前缀和路径向上汇总。这种对数时间复杂度的操作是BIT的最大魅力之一。
2. 高效实现方法与注意点
实现要点
在实现中，将数据结构设计为一个< denotes="true">一维整型/整型长整型数组，下标范围使用1..n，长度通常为n+1以容纳哑元。更新操作和<前缀和查询的时间复杂度均为O(log n)，且空间复杂度为O(n)。
另外一个重要点是构建过程：可以通过初始化为0再逐个调用add(i, delta)来构建，也可以提供一个buildFromVector方法快速从已有数组构造BIT，以降低初始耗时。要注意1-based下标对齐以及越界保护。
3. 代码示例：C++实现BIT（Fenwick Tree）
完整实现与使用
下面给出一个简洁且实用的C++实现，包含add、sum、sum(l, r)以及从向量构建的能力。该实现专注于<高效性与易用性，并且便于在实际项目中直接改造使用。
#include <iostream>
#include <vector>
using namespace std;// Fenwick Tree / Binary Indexed Tree
class Fenwick {int n;vector<long long> bit;
public:// 构造：n 为序列长度，bit 使用 n+1 长度，索引从 1 开始Fenwick(int n): n(n), bit(n+1, 0) {}// 将 delta 加到下标 idx（1-based）void add(int idx, long long delta) {for (; idx <= n; idx += idx & -idx)bit[idx] += delta;}// 以 idx 为端点的前缀和：sum(1..idx)long long sum(int idx) const {long long res = 0;for (; idx > 0; idx -= idx & -idx)res += bit[idx];return res;}// 区间求和：sum(l..r)，要求 1 <= l <= r <= nlong long sum(int l, int r) const {if (l < 1) l = 1;if (r > n) r = n;if (l > r) return 0;return sum(r) - sum(l - 1);}// 通过向量构建 BIT，向量长度 m 需小于等于 nvoid buildFromVector(const vector<long long> &a) {for (int i = 1; i <= n; ++i) bit[i] = 0;for (size_t i = 0; i < a.size() && i < (size_t)n; ++i)add((int)i + 1, a[i]);}
};int main() {// 示例数据vector<long long> arr = {1, 2, 3, 4, 5};Fenwick ft((int)arr.size());ft.buildFromVector(arr);// 前缀和查询cout << "前缀和(5) = " << ft.sum(5) << endl; // 1+2+3+4+5 = 15// 点更新：将下标3加上10ft.add(3, 10);// 更新后的前缀和cout << "前缀和(5) = " << ft.sum(5) << endl; // 1+2+13+4+5 = 25// 区间求和cout << "区间(2,4) = " << ft.sum(2, 4) << endl; // 2+13+4 = 19return 0;
}
4. 实战解析：应用场景与性能对比
应用场景与对比
在实际工程中，BIT（Fenwick Tree）最常用于需要快速更新数据同时快速计算区间前缀和的场景，例如动态数列的前缀和维护、实时统计、以及比赛中的分数区间查询等。通过O(log n)的时间复杂度实现，明显优于线性遍历的更新与查询方案，极大提升响应速度与吞吐量。区间前缀和查询通过 sum(r) - sum(l-1) 即可得到，极为直接。
与朴素的数组实现相比，BIT 的优势在于节省额外空间并降低时间成本；结合实际数据规模，当数据规模 n 达到几十万甚至上百万时，BIT 的优势尤为明显。本文给出的C++实现BIT在保证易用性的同时，保留了核心的高效路径：单点更新的对数复杂度与 前缀和查询的对数复杂度。
需要注意的是，BIT 主要支持前缀和与单点更新的场景。若需要同时实现区间更新和区间查询，通常需要引入双树结构或扩展的树状数组方案；在本文的实现中，若仅需要区间和和单点更新，直接使用一个 Fenwick Tree 已足够高效。
