浅谈树状数组

发布于 摸鱼世界

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就可以了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzypgs.html