树状数组Fenwick tree

用下标的最低有效位组织可复用的前缀聚合区间。

常见操作#

n 为数组长度；以加法和为例，整数宽度固定。

操作	时间复杂度	条件与说明
初始化为零	$O(n)$	建立 n 个聚合槽位。
单点增量更新	$O(\log n)$	沿 lowbit 对应的祖先区间累计增量。
前缀和 / 区间和	$O(\log n)$	区间和用两个前缀之差；依赖可逆运算。
从数组逐项加入	$O(n \log n)$	调用 n 次单点更新；专门的线性构建可以 $O(n)$ ，不是所有 API 都提供。
读取 / 覆盖一个位置	$O(\log n)$	通过前缀差取得当前值，再按差量更新；保留原数组可让读取为 $O(1)$ 。

不能直接把任意非可逆区间运算当作前缀差处理。

基础原理参考资料

AtCoder Library · Fenwick Tree初始化、增量更新、区间和以及类型限制。