树状数组

二叉索引树（Binary Indexed Tree, BIT），俗称树状数组，又称 Fenwick 树（因为作者是 Fenwick），是一种代码量小、易于实现的数据结构。

树状数组

树状数组的原理与 $\mathrm{lowbit}()$ 函数

#define lowbit(x) (x&-x)

根据 $\mathrm{lowbit}()$ 函数的特点，树状数组不能维护下标为 $0$ 的点。

单点修改区间查询 或 区间修改单点查询

C++Copy
void add(int u,int v){
	while(u<=n)a[u]+=v,u+=lowbit(u);
}
long long sum(int u){
	long long ans=0;
	while(u)ans+=a[u],u-=lowbit(u);
	return ans;
}

区间修改区间查询

设数列 $A$ 的差分数组是 $B$，则

$$\begin{aligned} \sum\limits_{i=1}^rA_i &= \sum\limits_{i=1}^r\sum\limits_{j=1}^iB_j \\ &= \sum\limits_{i=1}^rB_i \times (n-i+1) \\ &= (r+1) \times \sum\limits_{i=1}^rB_i-\sum\limits_{i=1}^nB_i \times i\end{aligned}$$

$O(n)$ 建树

以维护区间和为例：设原数列为 $a$，前缀和为 $s$（$s_i=\sum\limits_{j=1}^ia_j$），那么 $t_i=s_i-s_{i-\mathrm{lowbit}(i)}$。

模板题

例题：用树状数组维护区间信息

例题：树状数组与二分、倍增