zcmimi's blog

arrow_back二维树状数组共1篇文章

avatar
zc
2019-12-22 14:39:00
查看原题

点击跳转

此题卡常,需要使用二维树状数组

联想一维的树状数组:

差分数组:d_0=a_0,d_i=a_i-a_{i-1}(i>0)

令差分数组的前缀和sd_i=\sum_{j=0}^id_j,那么sd_i=a_i

我们现在来看看二维前缀和

s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)

查询(x_1,y_1)(x_2,y_2)的和则为:

s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1)

我们可以使用差分数组:

d(i,j)=a(i,j)-(a(i-1,j)+a(i,j-1)-a(i-1,j-1))

修改

d(x_1,y_1)+=v

d(x_1,y_2+1)-=v

d(x_2+1,y_1)-=v

d(x_2+1,y_2+1)+=v

举个例子:

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0 
0 0 0 0 0

1部分加上v,那么

0  0 0 0 0
0 +v 0 0 -v
0  0 0 0 0 
0 -v 0 0 +v

查询

对于点(x,y)它的值应该是:\sum\limits_{i=1}^x\sum\limits_{j=1}^y d(i,j)

那么(1,1)(x,y)的和就是:

$$

\sum{i=1}^x\sum{j=1}^y\sum{p=1}^i\sum{q=1}^j d(p,q) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times(x-i+1)\times(y-j+1) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times[(xy-xj+x)+(-yi+ij-i)+(y-j+1)] \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times (xy+x+y+1)-d(i,j)\times i(y+1)-d(i,j)\times j(x+1) + d(i,j)\times i \times j $$

我们需要维护d(i,j),d(i,j)\times i,d(i,j) \times j, d(i,j)\times i \times j

1/1
Search
search