树状数组比前缀和快在动态更新场景：前缀和单点修改需O(n)重建，而树状数组通过lowbit(x)=x&-x实现单点更新和前缀查询均仅O(log n)，其核心是每个下标i维护长度为lowbit(i)的区间和，查[1,i]时不断减lowbit、改i时不断加lowbit。
树状数组比前缀和快在哪？
普通前缀和每次修改都要 O(n)，而树状数组修改和查询都是 O(log n)。关键在它的底层结构——用二进制低位（lowbit）跳转，只维护部分区间和，避免全量更新。
-
lowbit(x)实际就是x & -x，比如lowbit(12)是 4（12 的二进制是 1100，最低位的 1 对应 2²=4） - 每个下标
i管理长度为lowbit(i)的区间：从i - lowbit(i) + 1到i - 所以查
[1, i]时不断减lowbit(i)，改i时不断加lowbit(i)
怎么写标准的树状数组模板？
别手写两套函数，统一用 1-based 下标，封装成 struct 最稳：
struct Fenwick {
vector<long long> tr;
int n;
Fenwick(int n_) : n(n_), tr(n_ + 1, 0) {}
int lowbit(int x) { return x & -x; }
void add(int i, long long v) {
for (; i <= n; i += lowbit(i)) tr[i] += v;
}
long long sum(int i) { // [1, i]
long long res = 0;
for (; i; i -= lowbit(i)) res += tr[i];
return res;
}
long long range_sum(int l, int r) { // [l, r]
return sum(r) - sum(l - 1);
}
};
- 初始化传入数组长度，内部开
n + 1避免下标越界 -
add是单点加，不是赋值；要初始化原数组，得对每个位置调用add(i, a[i]) -
sum(i)返回的是前缀和，不是下标i处的值
为什么 update 后 query 结果不对？常见踩坑点
最常出错的是下标和初始化逻辑：
- 原数组是 0-based，但树状数组必须 1-based：读入
a[0..n-1]后，要循环for (int i = 0; i < n; ++i) fw.add(i + 1, a[i]) - 修改操作误用赋值而非增量：想把位置
i改成v，不能直接add(i, v)，得先算差值：add(i, v - old_val) - 查询
[l, r]时传了 0-based 下标，导致sum(l-1)变成负数索引——务必确认所有接口参数是 1-based -
tr数组没初始化为 0，尤其重复使用同一个Fenwick实例时，容易残留上一轮数据
树状数组能处理哪些变体问题？
它不只限于整数加法：
立即学习“C++免费学习笔记（深入）”；
- 支持「单点改、区间查」，反过来「区间改、单点查」也能做（差分 + 树状数组）
- 支持 long long，但要注意
add参数类型和tr类型一致，混用 int/long long 容易溢出 - 无法直接支持区间乘、区间 min/max —— 那得换线段树
- 离散化坐标后可处理大范围下标（比如坐标值到 1e9），只要实际插入点数 ≤ 2e5，树状数组依然高效
真正难的不是写对四个函数，而是每次调用前心里清楚：当前下标是不是 1-based？这次是改值还是加增量？查询闭区间时端点有没有偏移？这些细节漏一个，结果就错得毫无征兆。
