树状数组
2025-12-19
Intro
普通的树状数组支持两个操作:
- 单点插入
- 区间查询前缀和
也就是说,树状数组维护的必须满足可减性。
Proof
对于一个数 x,我们可以将其二进制分解成:
x=2i1+2i2+⋯+2im
令 i1>i2>⋯>im,那么区间 [1,x] 可以划分成 logx 个小区间:
1. 长度为 2i1 的小区间 [1,2i1]
2. 长度为 2i2 的小区间 [2i1+1,2i1+2i2]
⋯
m. 长度为 2im 的小区间 [2i1+2i2+⋯+2im−1+1,2i1+2i2+⋯+2im]
容易发现,这些区间的共同特点是:若区间结尾为 R,区间长度就是 lowbit(R)。
由于每个区间都被右端点唯一确定,所以最多只有 n 个区间。
在数学层面上,我们已经能够知道每个区间是啥,令 ci=∑j=i−lowbit(i)+1i
那么怎么找到一个区间的子区间呢?x 一定能被表示成 (⋯010⋯00)2 这样的二进制数,这个时候的 x−lowbit(x)+1 其实就是 (⋯000⋯01)2,且 x−1 是 (⋯001⋯11)2,也就是我们可以通过每次给 x−1 去掉最后一位,得到的就是 x 的一个子区间。
同样的,我们可以找到 x 的父区间,若 x 是 (⋯010⋯0)2,它的父区间就是 (⋯100⋯0)2,因为 x 二进制有 logx 位,所以一次操作是 O(logn) 的。
Examples
AcWing 241. 楼兰图腾
题目传送门
这道题就是树状数组求逆序对简单应用。
考虑单点插入 yj(j<i),那么查询 yi−1 时所求得的就是前面比 yi 小的数。
由于要求 v 和 ^ 的形状,所以可以看中间点左右两边,用乘法原理算。
由于 y 是一个排列,所以不用进行离散化,直接做即可。
AcWing 243. 一个简单的整数问题2
题目传送门
在数组 a 的差分数组 b 中,想要对 a 的 [L,R] 区间加 c 只需要在 bL 加 c,bR+1 减 c。
如果要查询 [1,x],实际就是求 i=1∑xj=1∑ibj。
很明显不能直接求,考虑将其展开:
1. d1
2. d1+d2
⋯
x. d1+d2+⋯+dx
还是不好求,并且我们需要将其转换为前缀和的形式,考虑将空缺部分补齐,会发现整个矩阵就是 (x+1)×∑i=1xdi,需要减去的是 d1+2d2+⋯+xdx,也就是 ∑i=1xidi,这样就可以用两个树状数组维护了。
