树状数组方法介绍

《树状数组方法介绍》由会员分享，可在线阅读，更多相关《树状数组方法介绍（9页珍藏版）》请在文档大全上搜索。

1、树状数组简介一、前言我们平日里总是会遇到一些动态的求和问题，一些朴素的方法时间速度上很难让人满意，因此我们需要设计一些算法来解决所遇到的问题。1、 基本问题我们下面设法解决这个动态求和问题。我们定义 N 个整型变量组成的数组 v1.N，每次操作有两种：（1） 将vidx 增加 det（2） 求 2、 朴素解决朴素的解决这个问题，我们用数组记录当前的数值，然后依次求和。那么操作（1）的复杂度是 O(1)，操作（2）的复杂度是 O(idx)，令询问数为 Q ，则在最坏情况下为 O(QN)。这样的复杂度非常不理想，我们要对之优化！二、倍增，分割和优化很多时候在处理区间问题的时候，倍增思想都是非常常用

2、的，比如 RMQ和LCA问题，而分割方法也是一个有用的工具，比如线段树。我们知道线段树是能够解决上面这个基本问题的，但是考虑到线段树的代码比较复杂，这里我们讨论更轻松的方法。1、 第一个想法我们发现，在朴素算法中，操作（2）用了很多的时间，我们试着优化这个操作的算法。参照RMQ的思想，我们可以将一个区间分成一些长度为2的整次幂的小区间。我们定义fij 表示区间 I, i+2j-1 的和，那么如果我们能够得到所有 fij ，那么我们就能够在 O(log N) 的时间里计算出我们需要的和。具体方法如下：对于区间 L,R，我们找到最大的 p ，使得 2p <= R-L+1，而 sumL,L+2

3、p-1 = fLp，于是我们只要继续计算 L+2p,R就可以了。由于每次找最大的 p，因次至多计算 log N 次就能得到结果这就是倍增思想的应用。但是很不幸，我们再观察操作（1）的时候，我们发现由于和某一个位置相关的 fij 实在太多了，所以操作（1）的时间就花的过多了，问题并没有得到解决。看来我们并不能完全照搬 RMQ 问题的经验RMQ是静态问题，而这里是动态的。2、 化简问题我们回过头看我们研究的问题，我们只需要求 1,idx 的和，并不需要求出任意区间的和，所以我们保存了大量没用的 fij ，因此使得我们操作（1）所需要的时间过多。现在我们要删去我们不需要的 fij，让数据变得更加紧凑

4、。观察计算区间 1,R，我们找到最大的 p，满足 2p <= R，我们用到的f1p，之后我们会紧接着计算 2p+1,R，似乎我们跳过了所有的 fip (1<i<2p+1)，那么所有这样的 fip 是否会用到呢？答案是否定的。简单证明一下：反证法：假设计算区间为 1.R，上次使用的为fjq，当前区间为 2q+1,R，计算得到最大的p满足 2p + 2q <= R ，且有 2q +1 < 2p + 1。则 2p > 2q，2q <= R，因此上次得到的 q，必然不是最大 q，使得 2q <= R，p 比 q 更优。假设不成立。（证毕）接着我们不难归纳

5、得出，我们只可能用到 fip (i mod 2p = 1)。如下图。方块就表示一个对应的 fip ，即一段部分和。可以发现，现在，对于一个下标 idx ，最多只有 log N 个方块在其上方，因此在完成操作（1）的时候，我们只需要 Log N 的时间，就可以了。3、 进一步的化简对于区间 1,R，不难发现，我们是将区间划分成了至多 log N 块小区间，长度为 2p1，2p2，2p3 2pk。这里 pi > pi+1 ，即 p 序列是严格递减的。这正是因为我们每次都找出当前最大的 p 的缘故。于是，我们发现，上图中的红色方块其实也是不需要储存的。我们将其删去，就有了下图。整理后发现，每一

6、个数组元素和每一个fip一一对应。紧接着，我们用t数组记录每个数组元素对应的fip，而这就是树状数组。至此，我们从基于倍增思想的最朴素的分割方法，不断优化，最后得到了我们需要的东西。4、树状数组小史树状数组，Binary Indexed Tree，简称BIT，是1994年由Peter M. Fenwick首先提出的。BIT在快速求和方面有常数小、速度快、空间需求低、代码简洁等许多优点，很短时间便广泛流传。从英文来看，不难看出，BIT是一个tree，其实设计它的时候本身就是用树的理念设计的。我们如果加一个结点0为根，元素对应的覆盖区域若相邻便连边，很容易建立出这么一颗有根树。这个树的意义在于：对

7、于区间和 1,R，只要取出0-R的这条路径 ，并将路径上所有节点的值相加，就是要求的答案！我们称之为询问树（the interrogation tree）。而这棵树的深度是 Log N 级别的，宽度也是 Log N 级别的。其实还有一种更新树(The updating tree)，和询问树对应，我们这里暂且不讲，本文稍后会提到。树状数组正是基于这两颗树而工作的。而这Binary Indexed Tree为什么翻译后就成了“数组”，原因不详，据笔者理解应该是BIT在实现过程中多用数组，而且操作简便，于是其树的形式便被渐渐遗忘了吧。三、 技术实现下面我们要讨论如何在BIT这个Tree上“行走”。1

8、、 对应关系我们利用数组 t记录对应的部分和。L（i）表示ti对应的那个块的长度。下面需要解决的就是如何快速的计算出L（i）。我们写一张表来研究这个问题。I1234567891011I的2进制数写110111001011101111000100110101011L(I)12141218121L(I)的2进制书写1101100110110001101我们惊奇的发现，L(i)正是i 的2进制数表示中最后一个1所在数位的权！2、 朴素的计算最朴素的方式无非是枚举，这样需要 O(Log N)的时间，很是划不来。预处理也是一个好方法，我们可以利用下面的递推关系打出一张L(i)的表即可。但是这样似乎很不优

9、美，下面介绍优美的方法。3、 低位技术(Lowbit)我们利用位运算可以很优美的解决这一问题。先提一下第一种方法：方法1 ：L(I) = I AND (I XOR (I-1) )我们这样来表示 I 的2进制书写，a表示一些01的排列，b表示全为 0 的排列，c表示全为1的排列，a 表示a的反码（即a的某一位为0，a则在那一位为1，反之同理）。那么i一定能写成 (a1b) ，那么 i-1 则为 (a0c)。I XOR (I-1) 即 (a1b) XOR (a0c)，得到的是 (1c)。最后再 AND I，即 (1c) AND (a1b) 得到 (1b)。即我们要的答案。这是一种比较优美的方式，不

10、过利用了3次计算才得出结果，略有瑕疵。下面介绍更优美的方法：方法2 ：L(i) = I AND I （注意这里的 I 需要是有符号整数类型）这里利用了计算机中负数的储存原理，即 （K 1） = K补码。那么如果把 I 写成 (a1b) ，那么 I 即为 (a0c)，即 (a1b)。之后再 AND I 即 (a1b) AND (a1b) 得到 (1b)。这里只用了2次计算便得出结果，可以真正说的上是优美了。这也就是树状数组的最关键技术低位技术 (Lowbit)。4、 取出部分和对于区间1,idx，相当于我们在interrogation tree中的 idx 号结点需要“走”到 0 号结点，并将途

11、经的结点值累加。也就是我们要找到 BIT 中 idx 号结点的父亲结点 parent 。由于 parent 和 idx 的覆盖区间是相邻的，即 parent = idx L(idx)。于是这个求和的代码便呈现出来了。Function BIT_Get_Sum (idx)1. s ß 02. while (idx > 0) do3. s ß s + tidx4. idx ß idx L(idx)5. End while6. return s由于 while 循环至多执行 Log N 次，因此这段代码的时间复杂度是 O(Log N)。5、 修改部分和这个操作似乎在