这玩意大概咕了 114514 年了,csp 一轮后把它肝出来吧。
对于任意一个数,我们可以将它分解为若干个不同的 2 的正整数次幂,20 年 pj 的 T1 就有这个。例如 $7=4+2+1=2^2+2^1+2^0$。
而我所理解的树状数组就是建立在这个基础上的:
对于任意一个 $x$,设它拆分后为 $2^{b_1}+2^{b_2}+2^{b_3}+2^{b_m}$,则满足 $\sum\limits_{i=1}^x a_i = \sum\limits_{j=1}^m\sum\limits_{i=1}^{2^{b_j}} a_i$,那么我们求 $\sum\limits_{i=1}^x a_i$ 就可以说是降到了 $log$ 级别的时间复杂度。
那么这时候我们需要一个操作 lowbit
,它能找到 $x$ 转为二进制的所有 $1$。如果真的不了解 lowbit
,可以先去打基础。
lowbit(x)
,即找到目前 $x$ 转为二进制后从右往左数第一位 $1$,它等于 x & -x
。
那么现在树状数组就可以支持两个基本操作了:
1. 单点修改
2. 区间查询
单点修改:
当一个点需要修改时,它从右边第一个一起,它左边的所有 0 都应该修改,时间复杂度为 $log n$:
void add (int x, int y) {
for (; x < N; x += x & -x) c[x] += y;
}
区间查询:
当需要查询 $\sum\limits_{i=l}^r a_i$ 时,我们可以把它转成 $\sum\limits_{i=1}^r a_i - \sum\limits_{i=1}^{l-1} a_i$,所以怎么说还是从 $1$ 至 $n$ 的 $a_i$ 和。
int query (int x) {
int res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
拓展:
- 区间修改,单点查询:
这个很好做,差分就行。代码就不写了。
- 区间修改,区间查询:
从区间修改,单点查询入手。设 $b$ 为差分数组, 则 课改写为 $\sum\limits_{i=1}^x\sum\limits_{j=1}^{i} b_j = \sum\limits_{i=1}^x (x-i+1)\times b_i=(x+1)\sum\limits_{i=1}^x b_i-\sum\limits_{i=1}^x i \times b_i$,接着就很简单了吧。