树状数组的奇妙运用
数据结构
oi
树状数组是一种能够在线维护前缀和的数据结构, 其写法简单常数小... 不具体介绍了, 看看一些奇妙的操作吧.
人人都会的
- 单点修改, 区间查询: 基本维护前缀和
- 区间修改, 单点查询: 维护差分
区间修改, 区间查询
引入数组, 表示区间中需要加值的差分, 进行区间加法时, 就直接对操作, 对加上, 对减去. 查询前缀和时, 设为区间的元素和, 易得
发现我们需要维护, , 的前缀和. 代码可以这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| int suma[MAXN], sumd[MAXN], sumdi[MAXN];
void update(int* c, int pos, int x) { while (pos <= n) { c[pos] += x; pos += lowbit(pos); } }
void sum(int* c, int pos) { int res = 0; while (pos >= 1) { res += c[pos]; pos -= lowbit(pos); } }
void add(int l, int r, int x) { update(sumd, l, x); update(sumd, r + 1, -x); update(sumdi, l, l * x); update(sumdi, r + 1, -(r + 1) * x); }
int query(int l, int r) { return suma[r] + r * sum(sumd, r) + sum(sumdi, r) - (suma[l - 1] + (l - 1) * sum(sumd, l - 1) + sum(sumdi, l)); }
|
二维前缀和
首先, 由二维前缀和求矩阵的操作方法:
用树状数组维护二维前缀和的方法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| void update(int x, int y, int val) { while (x <= n) { int t = y; while (t <= m) { c[x][t] += val; t += lowbit(t); } x += lowbit(x); } }
int query(int x, int y) { int res = 0; while (x >= 1) { int t = y; while (t >= 1) { res += c[x][t] t -= lowbit(t); } x -= lowbit(x); } return res; }
|
因此不难做到二维单点修改, 矩阵查询.
二维矩阵修改, 矩阵查询
首先说明一下二维差分怎么写. 由二维前缀和的形式, 定义
因此
即可用二维树状数组维护差分.
比如给一个的矩阵中间的部分加上, 可以这么修改差分数组:
1 2 3 4 5
| 0 0 0 0 0 0 +x 0 0 -x 0 0 0 0 0 0 0 0 0 0 0 -x 0 0 +x
|
所以矩阵修改操作的写法:
1 2 3 4 5 6
| void add(int x1, int y1, int x2, int y2, int x) { update(x1, y1, x); update(x1, y2 + 1, -x); update(x2 + 1, y1, -x); update(x2 + 1, y2 + 1, x); }
|
为了实现二维区间修改和查询的操作, 我们可以类比一维的情况, 用差分来表示前缀和.
根据前面的套路, 我们统计每一个的出现次数, 可以展开两层:
也就是说, 我们需要维护
开四个树状数组即可. 这样用树状数组写, 常数会比线段树小一些.