解题报告 LOJ133-135 二维树状数组模板

前言

这几题都是二维树状数组的模板,不得不说树状数组真是个好东西,既好写速度又快常数还小。但是二维上的处理讲真搞到了我。也使我对差分和前缀和这两个好用的工具有了更深的理解

所有题目都是基于 n\times m 的零矩阵上进行的操作。

LOJ133 单点修改,区间查询

题目链接:https://loj.ac/problem/133

不难发现,我们需要处理的树状数组变成二维的信息之后,在每次的加和查询的操作时,都只需要多考虑一维就可以了,即循环多加一层,需要注意的是这时候就不能直接将传入的 xy 进行操作了,因为每一层关于 y 的内循环都要从 y 的初始值开始考虑

这里需要注意二维前缀和的技巧:如果需要求 (a,b)(c,d) 间的矩阵的和的话,假设 s_{i,j}(1,1)(i,j) 的前缀和,则答案为

s_{c,d}-s_{a-1,d}-s_{c,b-1}+s_{a-1,b-1}

具体的证明咕咕咕了,哪天有时间再写,其实就相当于把多加了减掉,多减了的加回来而已。

具体见下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];

void add(int x,int y,int d)
{
    for(int xx=x;xx<=n;xx+=lowbit(xx))
        for(int yy=y;yy<=m;yy+=lowbit(yy))
            f[xx][yy]+=d;//和一维的很像,但只是加了一维而已
    return;
}

ll sum(int x,int y)//查询操作也一样
{
    ll ans=0;
    for(;x>0;x-=lowbit(x))
        for(int yy=y;yy>0;yy-=lowbit(yy))
            ans+=f[x][yy];
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t,a,b,c,d,k;
    while(scanf("%d",&t)!=EOF)
    {
        if(t==1)
        {
            scanf("%d %d %d",&a,&b,&k);
            add(a,b,k);
        }
        else
        {
            scanf("%d %d %d %d",&a,&b,&c,&d);
            ll ans=sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

LOJ134 区间修改,单点查询

题目链接:https://loj.ac/problem/134

涉及区间修改的时候就需要用到差分了,二维的差分和一维的差分其实本质上没有任何的区别,具体的操作和二维前缀和的有些相似,也是咕咕咕改天写。

单点查询就只需利用 BIT 求出差分的前缀和就可以了,具体见下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];

void add(int x,int y,int d)
{
    for(int xx=x;xx<=n;xx+=lowbit(xx))
        for(int yy=y;yy<=m;yy+=lowbit(yy))
            f[xx][yy]+=d;
    return;
}

ll sum(int x,int y)
{
    ll ans=0;
    for(;x>0;x-=lowbit(x))
        for(int yy=y;yy>0;yy-=lowbit(yy))
            ans+=f[x][yy];
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t,a,b,c,d,k;
    while(scanf("%d",&t)!=EOF)
    {
        if(t==2)
        {
            scanf("%d %d",&a,&b);
            printf("%lld\n",sum(a,b));
        }
        else
        {
            scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
            add(a,b,k),add(a,d+1,-k),add(c+1,b,-k),add(c+1,d+1,k);//这里是差分的处理
        }
    }
    return 0;
}

LOJ135 区间修改,区间查询

题目链接:https://loj.ac/problem/135

到这里就比较麻烦了,二维线段树我不会打,怎么办呢?只能考虑用树状数组来同时照顾前缀和和差分了。

不妨令 a_{i,j}=\displaystyle\sum_{x=1}^i\sum_{y=1}^jd_{x,y},即 d 为二维差分数组,而我们又由前缀和的定义知道 s_{k,l}=\displaystyle\sum_{x=1}^k\sum_{y=1}^ja_{i,j},因此类比一维的情况,考虑用含有差分的式子来表示前缀和,数学推导过程如下,由于我很笨,所以有可能存在小瑕疵,而且过程很不简洁:

\begin{aligned}
&\sum_{k=1}^x\sum_{l=1}^ya_{k,l}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^k\sum_{j=1}^l d_{i,j}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^kd_{i,l}\times(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(x-k+1)(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy-ky+y-xl+kl-l+x-k+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy+x+y+1-l-k+kl-xl-ky)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times[xy+x+y+1-l(1+x)-k(1+y)+kl]\
=&(x+1)(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}-(x+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l-(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k+\sum_{k=1}^x\sum_{l=1}^yd_{k,l}kl
\end{aligned}

其中 a_{k,l}=\displaystyle\sum_{i=1}^k\sum_{j=1}^l d_{i,j}

所以需要维护四个 BIT,分别是 \displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}lk

每次修改的时候四个 BIT 要联动修改,当推出了公式之后,剩下的事情就很简单了,写出代码实现即可,我不会告诉你我抄错了我自己推的式子导致 WA 两次。注意不要漏了要乘的东西就可以了,代码如下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=2058;
ll f1[maxn][maxn],f2[maxn][maxn],f3[maxn][maxn],f4[maxn][maxn];
int n,m;

void add(ll x,ll y,ll d)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            f1[i][j]+=d,
            f2[i][j]+=x*d,
            f3[i][j]+=y*d,
            f4[i][j]+=x*y*d;
    return;
}

ll sum(ll x,ll y)
{
    ll ans1=0,ans2=0,ans3=0,ans4=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            ans1+=f1[i][j],
            ans2+=f2[i][j],
            ans3+=f3[i][j],
            ans4+=f4[i][j];
    return ans1*(x+1)*(y+1)-ans2*(y+1)-ans3*(x+1)+ans4;
}

int main()
{
    scanf("%d %d",&n,&m);
    ll t,a,b,c,d,x;
    while(scanf("%lld %lld %lld %lld %lld",&t,&a,&b,&c,&d)!=EOF)
    {
        if(t==1)
        {
            scanf("%lld",&x);
            add(a,b,x),add(a,d+1,-x),add(c+1,b,-x),add(c+1,d+1,x);
        }
        else
            printf("%lld\n",sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1));
    }
    return 0;
}

大概就是这么多,先睡了,明天再继续肝。

解题报告 P5057 [CQOI2006]简单题

题目内容

P5051

大意:维护一个初始为 0 的 0-1 序列,支持单点查询和区间取反操作

解题思路

这题可以使用线段树,但是为了减少码量可以使用树状数组,具体的思路是这样的:

由于每对一个区间取反一次,就相当于在这个区间加了 1,然后查询的时候相当于这个点是偶数就是 0,是奇数就是 1,这就将问题转化为了树状数组的区间修改单点查询——维护一个差分序列即可。

然后就过去了,跑的速度也是比较快的,而且比线段树好写简直不要太多

#include <cstdio>
#define lowbit(x) (x&-x)

const int maxn=1e5+5;
int n,m;
int t[maxn];

void add(int x,int d)
{
    while(x<=n)
    {
        t[x]+=d;
        x+=lowbit(x);
    }
    return;
}

bool query(int x)//查询操作,单点查询区间和并转化为 0-1 值
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans&1;//在这里转化
}

int main()
{
    scanf("%d %d",&n,&m);
    int c,x,y;
    while(m--)
    {
        scanf("%d %d",&c,&x);
        if(c==1)
        {
            scanf("%d",&y);
            add(x,1);
            add(y+1,-1);
        }
        else
            printf("%d\n",query(x));
    }
    return 0;
}