2020.03.23

前言

以前其实也有接触过树状数组,但当时只是以为自己学会了,实际上模板都没背下来。这几天再经过一些练习,对树状数组更加熟悉了。

y总:大多数数据结构难写,难调,难想,树状数组是一股清流,好写,好想。

今天就来说说树状数组。


正文

基本

首先认识树状数组能解决的基本问题:

1.单点修改

2.区间查询

就这两个了!区间修改&单点查询也是利用差分+这两种操作完成的。

树状数组的优势相较于普通数组,就是把修改和查询的时间进行了一个折中,把原来的修改$O(1)$,查询O$(n)$优化为了修改,查询都是$O(logn)$。

接下来讲讲是怎么理解并实现树状数组的。

对于树状数组,我们维护了一些区间和,暂时把它们叫做c[],原本的就叫做a[]吧。

假设当前要维护的数的总数为x,很显然(真的很显然),我们可以把x拆成若干个2的幂的形式相加。为了方便表达,$x=2^{i_k}+2^{i_{k-1}}+...+2^{i_1} \,$,并且$i$序列递减.$k<=log(n)$。

这样对于当前的x,如果我们维护这样k个区间,分别表示:$(x-2^{i_1},x],(x-2^{i_1}-2^{i_2},x-2^{i_1}]...,(0,x-2^{i_1}-...-2^{i_{k-1}}]$,就可以在$O(log(x))$的时间内求出1-x的前缀和了。

所以树状数组就是用来快速的维护这些区间的。

我们发现,右端点每次减去的二的次幂,恰好对应减去了上一次右端点二进制表示下的最后一个1

举个栗子。$(5)_2=101$,$5=2^2+2^0$,按照过程,第一个右端点减去的应该是$2^0$,得到$5-1=4,(4)_2=100$。第二个右端点减去的是$2^2$,得到$4-4=0,(0)_2=000$,两次操作,刚好把这两个1给对应减去了。

虽然看起来模拟很麻烦,但是在实际实现中,我们如果要找到这个数二进制下的最后一个1对应的数值,我们只需要用O(1)的时间计算。只需要这样写:

//声明包含库之后写
#define lowbit(x) (x&-x)
//或者写成这样函数的形式
int lowbit(int x)
{
    return x&-x;
}
//需要用的时候直接调用就好了

接下来就是怎么具体维护这个c[]的问题了。因为对于每一个右端点,区间的长度是固定的(lowbit(x)),所以我们只需要用右端点作为数组下标就好了,即c[R]=a[R-lowbit(R)+1~R]

接下来出场的是树状数组的经典例子。目的是为了更直观地看出在树状数组中各个节点(?)之间的关系。

树状数组演示.jpg

那现在如果要对某个单点进行修改的话应该怎么做呢?先考虑修改一个单点会影响到哪些c[]的值。

继续举例子。

比如我要修改a[1]的值,根据图片,很明显在这个例子中会影响到c[1],c[2],c[4],c[8]的值,它们全部都要变化。我们来观察这些数字的特性。首先把我要修改的下标和影响的下标都用二进制表示出来。

0001->0001,0010,0100,1000

发现什么了吗?再举个例子,这次修改a[5]的值。

0101->0101,0110,1000

是的,就是从当前这个下标开始,每次增加自己二进制表示下的最后一位对应的值。即i+=lowbit(i),直到超出序列总长度。

这样,单点修改操作就很容易完成了。

void add(int start,int value)
{
    for(int i=start;i<=n;i+=lowbit(i))
        c[i]+=value;
}

然后要考虑的,就是如何快速求前缀和。

依然通过举例子来发现规律。

1 求a[1]~a[7]的前缀和。

根据上面的图,我们需要返回c[7]+c[6]+c[4]的值。

0111->0111,0110,0100

2 求a[1]~a[5]的前缀和。

0101->0101,0100

我们发现,从起始位置开始,每次的下标都减去了二进制表示下的最后一位所对应的值

所以我们可以这样来实现:

int ask(int x)
{
    int tmp=0;
    for(int i=x;i;i-=lowbit(i))
        tmp+=c[i];
    return tmp;
}

要注意的是,询问得到的是存进去的数中的前缀和,所以如果要查询[l,r]区间的值,请用ask(r)-ask(l-1)得到。

洛谷模板题传送门


差分

洛谷模板题2传送门

不要问为什么还有2

可以看到,在原本的树状数组的基础上,它把基本操作变成了这样两个:

1.区间修改

2.单点查询

但是!树状数组在本质上还是只能维护单点修改&区间查询两个操作的,我们要怎么样才能把这两组操作之间完成一个转化呢?

先从单点修改->区间修改入手

如果在没有查询的题目里遇到区间修改的操作,我们会怎么做?当然是差分。如果要在[l,r]加上c,只需要a[r+1]-=c,a[l]+=c就可以了。

树状数组同理。再考虑单点查询。因为差分之后树状数组所求得的前缀和,也是差分数组的前缀和,恰好对应了需要查询的单点值,所以只需要在添加的时候不直接增加a[i],而是增加a[i]-a[i-1]。

参考代码


差分+公式

理解了上面的差分树状数组,接下来还有更毒瘤的哦~

ACwing例题

在上面的两个操作中,我们实际进行的操作都是一个单点+一个区间,两个操作都是单点就不用说了,如果两个操作都是要求在一个区间完成呢?

也就是说,我们的树状数组又要实现这两个功能:

1.区间修改

2.区间查询

首先,为了照样完成区间修改操作,差分的思想我们必须保留,否则挨个修改会使时间复杂度爆棚。

那么我们要怎么在差分的情况下完成区间查询呢?

我们先来分析一下问题。区间查询,本质上是求原本的a[]的前缀和。但是因为每一个a[]中的值都是以差分b[]的形式存储的,所以每一个a[]的值我们都要用一次$\sum_{i=1}^x b[i]$来求得,但是我们要求的是前缀和,所以我们每次查询要求的是这样一个玩意:

$\sum_{i=1}^x \sum_{j=1}^i b[i]$

我们发现,对于每一个b[i],它被累加的次数是一定的,这个时候用循环累加就很浪费时间。观察一下,每个$b[i]$在这个过程中,会被累加$(x-i+1)$次。看下面的图形就知道了。

b1
b1 b2
b1 b2 b3
b1 b2 b3 b4
...
b1 b2 b3 b4 b5 ... bx

于是我们的公式就可以变形成$\sum_{i=1}^x (x-i+1)*b[i]$。

再从括号里把-i项提取出来,得到$\sum_{i=1}^x (x+1)*b[i] - \sum_{i=1}^x b[i]*i$

于是,就变成了维护两个差分树状数组的问题了。

怎么样,刺激不刺激

重复具体解法:维护差分数组b[i]的树状数组c1[],再维护b[i]*i的树状数组c2[],更新的时候记得两个树状数组都要更新。

参考代码


二维树状数组

基本

这样的题目一般出现得比较少(或者是我孤陋寡闻了,了解一下就可以了。

ACWing例题传送门

如果只是基本操作,那就只是一维树状数组的一个简单拓展。在二维状态下,只需要把修改和查询的操作中都再添加一层循环即可。

void add(int x,int y,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
            c[i][j]+=k;
}
int ask(int x,int y)
{
    int tmp=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
           tmp+=c[i][j];
    return tmp;
}

唯一需要注意的地方是在求子矩阵的和的时候需要考虑,我们到底要怎么求得最终的矩阵。

比如我们想取[x1,y1,x2,y2]-(左上角右下角坐标)的时候,我们应该如何利用这个二维前缀和来求?

首先我们得到[x2,y2]的前缀和,发现多了一部分,我们要把它们减去。于是减去[x2,y1-1],[x1-1,y2]的前缀和,但是这样我们又把这两者重叠的部分多减去了。所以最后我们还要加上[x1-1,y1-1]的前缀和。

参考代码


差分

待更新

我们先回忆一下一维的差分是如何实现的。假装有一个差分数组b[i]=a[i]-a[i-1],并用树状数组来维护它的前缀和。

那么到了二维,我们怎么用差分来实现呢?首先,差分的本质就是做差(应该是吧)。

当前处理到了点(i,j),我们该如何计算它对应在差分数组中的值?

d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

背就完了

另外,二维前缀和公式:$c[i][j]=a[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1]$

代码块如下:

void radd(int x,int y,int xx,int yy,int v)
{
    add(x,y,v);
    add(x,yy+1,-v);
    add(xx+1,y,-v);
    add(xx+1,yy+1,v);
}

其他操作就是基本的二维树状数组的操作。只是对于差分数组的初始化有所不同而已。

例题POJ-2155 Matrix

这道题目的大意是这样:t组数据,n×n的01矩阵,初始为0,m条操作,C x1 y1 x2 y2是把这个子矩阵全部翻转,Q x y是查询点(x,y)的值。

其实很简单,连值都不需要传,把c[i][j]+=v改为c[i][j]++,询问的时候记得对2取模就可以了。

参考代码


差分+公式

待更新

毒瘤更加毒瘤

先来看下面这样一个问题:

例题 洛谷P4514 上帝造题的七分钟

在这个问题中,我们需要在二维下完成两种操作:

1.区间修改

2.区间查询

这是不是和一维差分+公式解决的问题类似?都是要解决两个区间操作的问题。那我们就以类似的思路来考虑这个问题的实现。

在一维里,我们保留了差分,对于区间查询,找到了其中数字出现的次数规律,减少了循环层数,那这个问题是不是也可以这样呢?

我们先来缕清解决的思路。二维差分的形式依然保留,问题转化到了如何求子矩阵的数值之和。

如果是单点查询,我们就需要求$\sum_{i=1}^x \sum_{j=1}^y c[i][j]$。

如果是区间查询,我们不添加任何修改的话,我们就需要用四层循环,求这样一个东西:

$\sum_{i=1}^x \sum_{j=1}^y \sum_{h=1}^i \sum_{k=1}^j c[h][k]$

但是很明显,会超时掉。那么我们就和之前一样,来找一下每个数出现次数的规律。

我们就从个体出发,研究出现次数

c11 x*y次
c12 x*(y-1)次
...
c21 (x-1)*y次

所以c[h][k]共会出现(x-h+1)*(y-k+1)次。我们把这个数据再带入上面的式子,就可以得到:

$\sum_{i=1}^x \sum_{j=1}^y c[i][j]*(x-i+1)*(y-j+1)​$

当然,这样化简之后我们依然不能快速的求出它的值,所以我们把后面的$(x-i+1)*(y-j+1)$拿来展开如下:

$(x-i+1)(y-j+1)=(x*y+x+y+1)-(x*j+j)-(y*i+i)+(i*j)$

$=(x+1)(y+1)-((x+1)*j)-((y+1)*i)+(i*j)$

所以我们就把这个式子拆成了四项,再把这四项分配到原来的求和上面去:

$\sum_{i=1}^x \sum_{j=1}^y c[i][j]*((x+1)(j+1)-((x+1)*j)-((y+1)*i)+(i*j))$

$=(x+1)*(y+1)*\sum_{i=1}^x \sum_{j=1}^y c[i][j]-(x+1)*\sum_{i=1}^x \sum_{j=1}^y c[i][j]*j-$

$(y+1)*\sum_{i=1}^x \sum_{j=1}^y c[i][j]*i+\sum_{i=1}^x \sum_{j=1}^y c[i][j]*i*j$

所以思路很明显了,分别维护存放c[][],c[][]*i,c[][]*j,c[][]*i*j的树状数组,需要的时候用差分累加即可。此外,每次更新的时候就需要注意四个树状数组都要更新哦。如果有题目的数据比较大的,还要注意long long类型的定义。

代码块如下:

void add(int x,int y,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
        {
            c1[i][j]+=(v);
            c2[i][j]+=(v*x);
            c3[i][j]+=(v*y);
            c4[i][j]+=(v*x*y);
        }
}
void radd(int x,int y,int xx,int yy,int v)
{
    add(x,y,v);
    add(x,yy+1,-v);
    add(xx+1,y,-v);
    add(xx+1,yy+1,v);
}
int ask(int x,int y)
{
    
    int tmp=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            tmp+=((x+1)*(y+1)*c1[i][j]-(y+1)*c2[i][j]-(x+1)*c3[i][j]+c4[i][j]);
    return tmp;
}
int query(int x1,int y1,int x2,int y2)
{
    return ask(x2,y2)-ask(x1-1,y2)-ask(x2,y1-1)+ask(x1-1,y1-1);
}

和上面的思路完全一样,模板题。就是注意要卡一下快读+开O2才能过(如果您会卡时间请无视)。

参考代码


基本完结

这只是树状数组的模板学习,很多情况下,这些问题都不太容易看出是用树状数组解决,所以多见识题目才是王道哦。

后续如果有相关算法,再进行更新吧(咕了)。

最后修改:2020 年 04 月 19 日 09 : 51 PM