树状数组

定义

满足以下功能的树状数组结构：

单点修改
区间查询 满足以下特征：
代码量小
维护的信息 & 运算满足：
- 结合律：$(x \circ y) \circ z = x \circ (y \circ z)$
- 可差分：运算具有逆运算，已知 $x \circ y$ 和 $y$ 可推 $x$。

单点修改，区间查询

对于给定数据数组 $a[n]$ ，树状数组提供缓存数组 $c[n]$ 缓存区间信息。

$c[i]$ 的管辖区间应为 $[i + \mathrm{lowbit}(i) .. i]$，即： $$ c[i] = \mathrm{opt}{a[i - \mathrm{lowbit}(i) + 1 .. i]} $$

Lowbit

$\mathrm{lowbit}$ 运算是指一个数只保留在二进制下最低位的 1 ，其余位为 0 所构成的二进制数。

根据二进制知识有：

1

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

区间查询结果根据缓存信息结合构成，因此要求结合律。