二维树状数组 学习笔记

前言:遇到二维的问题都很虚,而且树状数组也不熟练……于是学了一发这个。

——————————

以下所有问题均在二维中

1.单点修改,单点查询

这个最简单,直接开一个二维数组搞一搞就完事了。

2.单点修改,区间查询

回想一下一维的树状数组是怎么搞的:我们维护序列的前缀和;查询区间的时候直接让前缀和相减就好。放到二维也是同理。给出区间查询的式子:

$ans=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)$

代码:

inline void add(int x,int y,int k)
{
    for (int i=x;i<=n;i+=lowbit(i))
        for (int j=y;j<=m;j+=lowbit(y))
            tree[x][y]+=k;
}
inline int sum(int x,int y)
{
    int ans=0;
    for (int i=x;i>0;i-=lowbit(i))
        for (int j=y;j>0;j-=lowbit(j))
            ans+=tree[x][y];
    return ans;
}

3.区间修改,单点查询

回想一下一维的树状数组是怎么维护的:我们维护$a[i]$的差分数组$d[i]$;让区间$[l,r]$加$k$就让$d[l]$加$k$,$d[r+1]$减$k$。求和就是$a[i]=sumlimits_{j=1}^i d[j]$。放到二维也是一样,差分数组的意义变成如下:

$d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$(类比二维前缀和)

比如我们想让$(2,2,3,4)$之间的部分加$1$:

原先是这样的:

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

做一下差分:

0  0  0  0  0
0  1  0  0  -1
0  0  0  0  0
0 -1  0  0  1

代码:

inline void add(int x,int y,int k)
{
    for (int i=x;i<=n;i+=lowbit(i))
        for (int j=y;j<=m;j+=lowbit(y))
            tree[x][y]+=k;
}
inline int sum(int x,int y)
{
    int ans=0;
    for (int i=x;i>0;i-=lowbit(i))
        for (int j=y;j>0;j-=lowbit(j))
            ans+=tree[x][y];
    return ans;
}
inline void update(int x1,int y1,int x2,in y2)
{
    add(x1,y1,1);
    add(x2+1,y1,-1);
    add(x1,y2+1,-1);
    add(x2+1,y2+1,1);
}

4.区间修改,区间查询

这个我一维树状数组也没干过这个,都是拿线段树写的……直接推式子吧。

我们还是维护差分数组。想求$(1,1,x,y)$内所有数和,我们有:

$ans=sumlimits_{i=1}^x sumlimits_{j=1}^y sumlimits_{k=1}^i sumlimits_{h=1}^j d[k][h]$

考虑每个$d$算了多少次,我们可以化简得到:

$ans=sumlimits_{i=1}^x sumlimits_{j=1}^y d[i][j]*(x-i+1)*(y-j+1)$

$ans=(x+1)*(y+1)sumlimits_{i=1}^x sumlimits_{j=1}^y d[i][j]-(x+1)sumlimits_{i=1}^x sumlimits_{j=1}^y d[i][j]*j-(y+1)*sumlimits_{i=1}^x sumlimits_{j=1}^y d[i][j]*i+sumlimits_{i=1}^x sumlimits_{j=1}^y d[i][j]*i*j$

然后用四个树状数组分别维护一下就行了。

代码:

inline void add(int x,int y,int z)
{
    for (int i=x;i<=n;i+=lowbit(i))
        for (int j=y;j<=m;j+=lowbit(j))
            tree1[i][j]+=z,tree2[i][j]+=z*x,tree3[i][j]+=z*y,tree4[i][j]+=z*x*y;//这里我不太懂为什么乘的是x和y……明白了会补上
}
inline int sum(int x,int y)
{
    long long ans=0;
    for (int i=x;i>0;i-=lowbit(i))
        for (int j=y;j>0;j-=lowbit(j))
            ans+=tree1[i][j]*(x+1)*(y+1)-tree2[i][j]*(y+1)-tree3[i][j]*(x+1)+tree4[i][j];
    return ans;
}

 

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 二维树状数组 学习笔记

发表评论

免登录下载网,提供全网最优质的资源集合!