首页 > 代码库 > 浅谈二维中的树状数组与线段树

浅谈二维中的树状数组与线段树

一般来说,树状数组可以实现的东西线段树均可胜任,实际应用中也是如此。但是在二维中,线段树的操作变得太过复杂,更新子矩阵时第一维的lazy标记更是麻烦到不行。

但是树状数组在某些询问中又无法胜任,如最值等不符合区间减法的询问。此时就需要根据线段树与树状数组的优缺点来选择了。

做一下基本操作的对比,如下图。

因为线段树为自上向下更新,从而可以使用lazy标记使得矩阵的更新变的高校起来,几个不足就是代码长,代码长和代码长。

对于将将矩阵内元素变为某个值,因为树状数组自下向上更新,且要满足区间加法等限制只能将其分解成n*m次单点更新。

基本操作就是这些,下面说一下怎么实现这些操作。


树状数组(此部分摘自wyl8899《树状数组维护区间和的模型及其拓广的简单总结》):

从一维的区间更新,单点查询开始讲起。

一维的时候可以建立辅助数组d[1] = a[1] , d[i] = a[i] - a[i-1],则此时a[i] = d[1] + d[2] + ......+d[i]。则,

对a[] 的单点查询就变成了d[]的前 i 项和查询;

对a[]的成段更新变成了对d[]的两次单点更新,如要在a[]的[l,r]上加上w,即为d[l] += w,d[r+1] -= w,维护一下d[]对应的树状数组就好了。

接下来是一维的区间更新,区间查询。

假设求a[]的前i项和,会有

sum = a[1] + a[2] + ......+ a[i] = i*d[1] + (i-1)*d[2] +......(i-x+1)*d[x]+......+1*d[i] = sigma(i-1)*d[x] - sigma(x*d[x]) = (i-1)*sigma(d[x]) - sigmax*d[x]   ( 1<= x && x <= i)。

所以只需要再加一个辅助数组来维护x*d[x]。

如此,则对于a[]的区间操作均转化成了对d[]和x*dx[]的单点操作。

二维的情况:

现附上单点更新及区间查询的模板。

int sum(int a[maxn][maxn],int x,int y){
  int s=0,t;
  for(;x;x-=lowbit(x))
    for(t=y;t;t-=lowbit(t))
      s+=a[x][t];
  return s;
}
void updata(int a[maxn][maxn],int x,int y,int w){
  int t;
  for(;x<=n;x+=lowbit(x))
    for(t=y;t<=m;t+=lowbit(t))
      a[x][t]+=w;
}

然后继续挖掘树状数组的性质,一个很浅显的性质。

首先一维的时候,若对a[i] += w,那么a[]的前x(1 <= x <= n)项和均会加w。

二维的时候显然也是这样,则我们用a[x][y]表示原数组A[][]从(x,y) --(n,m)的变化。

则对A[][]的单点A[x][y]的查询转化为求a[][]的(1,1)--(x,y)的和。


现在来说矩阵加减,矩阵求和,仍用a[][]表示A[][]的变化。

则A[][]的(1,1)--(x,y)的和为sum = sigma(a[i][j] *(x-i+1)*(y-j+1))(1 <= i <= x ,1 <= j <= y)。

因为a[i][j]表示A[][]从(i,j)--(n,m)的变化,而到(i,j)--(x,y)有(x-i+1)*(y-j+1)个元素,故得上述式子。


将上式展开后得(x+1)(y+1)sigma(a[i,j]) - (x+1)sigma(a[i,j]*j) - (y+1)sigma(a[i,j]*i) + sigma(a[i,j]*i*j)。

同一维,用四个辅助数组记录sigma(a[i,j]) ,sigma(a[i,j]*j), sigma(a[i,j]*i) , sigma(a[i,j]*i*j)。


具体代码见http://blog.csdn.net/zmx354/article/details/31759121


线段树:

首先是树的样子,对第一维建立一棵线段树T1,T1的每个节点均对应一棵线段树Ti2(i表示t1的节点编号),Ti2对应第二维。

然后是初始化,以求num[][]的最大值为例。

设s1,s2分别为T1,T(s1)2的节点编号。

若s1,s2均为叶子结点,则st[s1][s2] = num[x][y],以为此时st[s1][s2]对应的就是一个点。

若只有s1为叶子结点,则有st[s1][s2] =  max(st[s1][s2<<1],st[s1][s2<<1|1])。

若都不是叶子结点则有,st[s1][s2] = max(st[s1<<1],st[s2],st[s1<<1|1][s2])。


单点更新:

首先是第一维找到对应结点site,则site到root路径上所有Ti2均要更新,一共更新log(n)*log(m)。

区间更新,加两个lazy标记,第二维的就是一维线段树中的。第一维不同之处在于需要记录当前更新中第二维的范围。

更新是也要讨论s1,s2是否为叶子结点。学的时候被这里卡了好久,有一次和zp扯淡的时候突然顿悟了。


关于查询就不说了,这是最像一维的了。


以上均为弱菜的井底之见,不足之处,敬请指出。