树状数组

学习。

首先，记住这个图（from OI-wiki）：

普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。

基本操作

单点修改 区间查询

int lowbit(int x) { return x & -x; }
void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; }
int sum(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }

区间修改 单点询问

// 前置函数如上 利用差分原理
add(l, x), add(r + 1, -x);
sum(x);

也可以用两个树状数组维护，处理区间修改，区间访问问题。（但这种情况一般用线段树）

具体应用

Eg1：用树状数组维护线段1~n，动态查询出现的个数。楼兰图腾 - AcWing

Eg2：用树状数组维护线段1~n，结合二分动态查询线段上第k + 1个不为1的数。谜一样的牛 - AcWing