RainAir
My OI Blog
RainAir
二维树状数组学习笔记

我们把树状数组由一维扩展到二维。二维树状数组的定义是:
$C[x][y] = \sum A[i][j]$,其中
$x – lowbit(x) + 1 \leq i \leq x$
$y – lowbit(y) + 1 \leq j \leq y$
所以我们就可以很方便的写出来单点修改和查询 $(1,1)$ 到 $(x,y)$ 的和的代码了:

那我们来考虑如何维护这样一个操作:二维矩阵整体加,查询矩阵和。
二维线段树肯定是可以做的,但是写起来太麻烦,甚至可能会爆空间。
我们想一下在一维树状数组里,我们维护区间加是通过差分原数组来实现的。
注意到一维下差分的性质:定义 D 为 A 的差分数组,则 $A_x = \sum_{i=1}^x D_i$
所以说我们可以类比一维,定义二维下差分数组为:$D_{i,j} = A_{i,j}-A{i,j-1}-A_{i-1,j}+A_{i-1,j-1}$。
我们考虑考虑修改操作。通过差分数组的定义不难得出我们修改 $(a,b)$ 到 $(c,d)$ 矩阵时,我们应该在差分数组的 $(a,b)$ 和 $(c+1,d+1)$ 加上 $delta$,同时在 $(a,d+1)$ 和 $(c+1,b)$ 减去 $delta$。
那我们如何处理询问操作呢?
我们不妨先写出最暴力的处理 $(1,1)$ 到 $(x,y)$ 的和,然后逐步优化。
根据差分数组的定义可得:
$$\sum_{i=1}^x \sum_{j=1}^y \sum_{h=1}^i \sum_{k=1}^j d_{h,k}$$
考虑差分数组每一位对答案的贡献,我们可以把其优化为二层枚举:
$$\sum_{i=1}^x \sum_{j=1}^y d_{i,j} * (x-i+1) * (y-j+1)$$
略微拆一下式子,可以得到
$$\sum_{i=1}^x \sum_{j=1}^y d_{i,j} * (x * y+x+y+1) – d_{i,j} * i(y+1) -d_{i,j} * j(x+1) + d_{i,j} * ij$$
用四个树状数组分别维护一下 $d_{i,j},d_{i,j} * i,d_{i,j} * j,d_{i,j} * i * j$ 即可。
一个题目链接
不过貌似这个东西常数比较大,在 Luogu 要开 O2 和读入优化……

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/471
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望省选不要翻车,希望我还有脑子
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

二维树状数组学习笔记
我们把树状数组由一维扩展到二维。二维树状数组的定义是: $C[x][y] = \sum A[i][j]$,其中 $x - lowbit(x) + 1 \leq i \leq x$ $y - lowbit(y) + 1 \leq j \leq y$ 所以我们就可以很方…
扫描二维码继续阅读
2019-02-07
文章归档