福州市工程建设质量管理协会网站,wordpress 5.0文章编辑教程,室内设计方案图,seo sem 做网站二维树状数组可以实现在平面上的区域加、区域查询等操作。 区域修改 我们在一维时维护树状数组的区间操作时#xff0c;对其进行了差分。类比一维的思想#xff0c;我们在二维平面上也对树状数组差分。 我们来看二维的前缀和#xff1a; \[sum(i,j)sum(i-1,j)sum(i,j-1)-sum… 二维树状数组可以实现在平面上的区域加、区域查询等操作。 区域修改 我们在一维时维护树状数组的区间操作时对其进行了差分。类比一维的思想我们在二维平面上也对树状数组差分。 我们来看二维的前缀和 \[sum(i,j)sum(i-1,j)sum(i,j-1)-sum(i-1,j-1)a(i,j) \]可以使二维差分数组为这样的形式 \[d(i,j)a(i,j)-d(i-1,j)-d(i,j-1)d(i-1,j-1) \](发现了吧这其实就是) 比如我们有一下这个全为 \(0\) 的矩阵那么给中间 \(2\times 3\) 的矩阵差分后长成这样(“o” 表示操作区域) 0 0 0 0 0 0 0 0 0 0
0 o o o 0 - 0 x 0 0 -x
0 o o o 0 0 0 0 0 0
0 0 0 0 0 0 -x 0 0 x 这样我们就简单地完成了区域加的操作。 区域查询 根据差分数组的定义我们不难发现对于点 \((x,y)\) 它的二维前缀和就是: \[\sum_{i1}^x\sum_{j1}^y\sum_{h1}^i\sum_{k1}^j d[h][k] \]但我们类比一下一维树状数组的区间求和我们亦可以统计每个 \(d[h][k]\) 出现的次数我们就可以发现 \(d[1][1]\) 出现了 \((x\times y)\) 次\(d[1][2]\) 出现了 \(x\times(y-1)\) 次……\(d[h][k]\) 出现了 \((x-h1)\times (y-k1)\) 次。 则原式整理得 \[\sum_{i1}^x\sum_{j1}^y d[i][j]\times (x-i1)\times (y-j1) \]分解得 \[\sum_{i1}^x\sum_{j1}^y d[i][j]\times [(xy-xjx)(-yiij-i)(y-j1)] \]最后得 \[\sum_{i1}^x\sum_{j1}^y d[i][j]\times (xyxy1)-d[i][j]\times i(y1)-d[i][j]\times j(x1)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\) 从而实现区间查询。 例题 — P4514 上帝造题的七分钟 即二维树状数组裸题。 $\texttt{code}$ #define Maxn 2050
int n,m,tree[Maxn][Maxn][4];
inline void add(int x,int y,int k)
{int ak,bk*x,ck*y,dk*x*y;for(int ix;in;ii(-i))for(int jy;jm;jj(-j)){tree[i][j][0]a;tree[i][j][1]b;tree[i][j][2]c;tree[i][j][3]d;}
}
inline int query(int x,int y)
{int ret0,ax*yxy1,by1,cx1,d1;for(int ix;i;i-i(-i))for(int jy;j;j-j(-j)){rettree[i][j][0]*a;ret-tree[i][j][1]*b;ret-tree[i][j][2]*c;rettree[i][j][3]*d;}return ret;
}if(修改) add(a,b,x),add(a,d1,-x),add(c1,b,-x),add(c1,d1,x);
else printf(%d\n,query(c,d)-query(a-1,d)-query(c,b-1)query(a-1,b-1)); 参考文章
