利用树状数组解决几类问题

《利用树状数组解决几类问题》由会员分享，可在线阅读，更多相关《利用树状数组解决几类问题（10页珍藏版）》请在金锄头文库上搜索。

1、利用树状数组解决几类问题浙江省温岭中学 林希树状数组作为一种实现简单、应用较广的高级数据结构，在 OI 界的地位越来越重要， 下面我来简单介绍一下树状数组和它的简单应用。一、树状数组简介一、树状数组简介树状数组(Binary Indexed Trees，简称 BIT)是一种特殊的数据结构，这种数据结构 的时空复杂度和线段树相似，但是它的系数要小得多。它可以方便地查询出一段区间中的 数字之和。其查询和修改的时间复杂度均为 O(lbN),并且是一个在线的数据结构，可以随时 修改并查询。我接下来用一道题目来介绍树状数组的几个基本操作。 【引例引例】 假设有一列数Ai（18 由此得出，c3、c4、c8

2、亦应该添加 x。 定理的证明如下：定理的证明如下： 【引引 理理】若若 Ak所牵动的序列为所牵动的序列为 Cp1，Cp2 Cpm，且且 p1 li 的数（若出现 Pi+x 比 pi+1更小，则 x0 DoBeginSum:=CN+Sum;N:=N-Lowbit(N);End; End;和其他高级数据结构一样，树状数组也支持求第 k 小元素、删除以及插入操作（这些一 直不被人熟知)，下面我来重点介绍一下： 【操作操作 4】删除操作：删除操作：Delete(k) 我们设 Ci表示数 i 出现的次数，删除第 k 个数只需要 Dec(CAk)即可（如果 Ak很 大，只需要离散化即可） 。 代码代码 P

3、rocedure Delete(K:Longint); Begin Modify(Ak,-1); End;【操作操作 5】插入操作：插入操作：Insert(k) 类似地，我们设 Ci表示数 i 出现的次数，插入第 k 个数只需要 Inc(CAk)即可（如 果 Ak很大，只需要离散化即可） 。 代码代码 Procedure Insert(K:Longint); BeginAdd(Ak,1); End;【操作操作 6】取第取第 K 小的数：小的数：FindKth(K) 同操作 4，我们设 Ci表示数 i 出现的次数。如果要求出最小值，也就是说我们需要找出一个最小的 i，使得，这个 i 必定是最小值

4、。接下来就是如何找出这个 i 的问 ijiC11题了。令，我们可以发现 S 具有单调性，于是我们可以通过二分查找来找 ijiCiS1出这个 i. 代码代码 Function FindKth(K:Longint):Longint; Var Left,Right,Mid,tmp:Longint; BeginLeft:=1; Right:=MaxValue;While Left0即可。我们可以发现前两个操作的时间复杂度均为O(1)，而第三个操作的时间复杂度接近于 O(S)。显然我们只要将操作3的时间复杂度降下来就可以了。注意到这道题目只需要求和， 这时候树状数组就派上了巨大的用场。构建一个树状数组C

5、： 对于操作A_i_a：我们只需要Add(hpi,-1)，Add(hpi-a,1)即可，同时将hpi减a。要 特殊考虑hpi-a小于等于0的情况； 对于操作C_i_a：我们只需要Add(hpi,-1)，Add(hpi+a,1)即可，同时将hpi加a； 对于操作Q_k：我们可以使用二分查找来找到那个数x（实现方式和找最小值一样）。至此，我们只需要将所有的数先离散化就可以了。时间复杂度：O(MlbN)3.“图腾图腾”类问题的统计类问题的统计 【例例 5】逆序对逆序对 描述描述 对于一个包含 N 个非负整数的数组 A1.n，如果有 i A j ，则称(A i ,A j )为数组 A 中的一个逆序对。

6、例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2), (5,2)，共 4 个。给定一个数组，求该数组中包含多少个逆序对。 输入输入 输入数据第一行包含一个整数 N，表示数组的长度； 第二行包含 N 个整数。 输出输出 输出数据只包含一个整数，表示逆序对的个数。分析分析 如题，这道题目只要求输出逆序对的个数就可以了，传统的求逆序对的方法有好多，这 里我只介绍用树状数组求逆序对。 设 Ci(i 如果会很大，只需要离散化即可)表示 i 出现的次数。我们顺序枚举每一个数 Ai，显然以 Ai为结尾的逆序对的个数为，这一步我们可以利用树状数组优化到 iAjjCO(lbN)，接下来

7、 inc(CAi)。将所有的加起来就可以计算出答案了。 iAjjC【例例 6】TYVJ P1432楼兰图腾楼兰图腾 描述描述 在完成了分配任务之后，西部 314 来到了楼兰古城的西部。相传很久以前这片土地上(比 楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹()，他们分 别用 V 和的形状来代表各自部落的图腾。 西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 N 个点，经测量 发现这 N 个点的水平位置和竖直位置是两两不同的。西部 314 认为这幅壁画所包含的信息 与这 N 个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),(n,

8、yn),其中 y1yn 是 1 到 N 的一个排列。如图，图中的 y1=5,y2=1,y3=2,y4=4,y5=3. 西部 314 打算研究这幅壁画中包含着多少个图腾，其中 V 图腾的定义如下（注意：图腾 的形式只和这三个纵坐标的相对大小排列顺序有关）1yj,yjyk; 西部 314 想知道，这 N 个点中两个部落图腾的数目。因此，你需要编写一个程序来求出 V 的个数和的个数。 输入输入 第一行一个数 N； 第二行是 N 个数，分别代表 y1，y2yn 输出输出 两个数，中间用空格隔开，依次为 V 的个数和的个数分析分析 我们可以发现，如果能统计出 V 图腾的个数，那么图腾的个数也可以利用类似

9、的方法 统计出来，这里我介绍两种方法来统计 V 图腾的个数。 方法一：方法一： 我们可以发现 V 图腾的前半部分具有逆序对的性质，因此我们可以利用类似的方法统计 V 图腾的个数。设 f1,i表示数 i 出现的次数，f2,i表示以数 i 为结尾的“”图腾的个数， f3,i表示以数 i 结尾的 V 图腾的个数。接下来我们顺序枚举 Yi，然后就是 f1.3的转移：111, 2, 3, 1 , 21, 1 , 1 iyjniyjjfiyfjfiyfiyfiyf最后的答案就是，用树状数组优化这个方程就可以将时间复杂度降为 niifans1, 3O(NlbN)。方法二：方法二： 我们可以从另一个角度来考虑

10、。我们仔细观察一下图形，V 图腾要求两边的点的高度大 于中间的点的高度。也就是说定下了中间的点之后，我们只需要分别统计这个点左边和右 边比他高的点的个数就可以了（分别设为 LS 和 RS） 。根据乘法原理，以这个点为中间点的 V 图腾的个数就是 LS*RS。显然我们的答案就是。至于计算 RS12*NiiRSiLSans和 LS 的过程中，我们只需要用树状数组来优化就可以了。 在实际运行效果中，虽然两种方法的时间复杂度都是 O(NlbN)，但方法一花的时间远超 过方法二。这就告诉我们，在平时做题目的时候，要多多注意分析各种算法的时空复杂度， 尽量使算法完美。【例例 7】K 阶逆序对阶逆序对(原创

11、题原创题) 描述描述 Jim 是一位数列爱好者，他对于各种数列都有一定的研究。同时他对和数列有关的数也特别感兴趣，最近他开始研究逆序对。 先给出逆序对的定义：对于一个包含 N 个正整数的数组 A1.N，如果有 i Aj，则称为数组 A 中的一个逆序对。例如，数组3,1,4,5,2的逆序对有 ,，共 4 个。 同许多牛人一样，Jim 很快解决了求一个给定序列的逆序对个数的问题。但 Jim 并不满 足这一点，他开始研究逆序对的推广形式：K 阶逆序对。下面给出 K 阶逆序对的定义：对 于一个包含 N 个正整数的数组 A1.N，如果存在一个序列 B1.K，有 1AB2ABK，则称为数 组 A 中的一个

12、 K 阶逆序对。 Jim 想知道对于一个给定的序列 A1.N，到底存在多少个 K 阶逆序对？Jim 在研究了 K=2,3,4,的情况之后，发现这个问题十分复杂。于是他找到了 OIT，希望你能帮助他解 决这个问题。由于 Jim 不喜欢看到高精度数，你只需要告诉他这个数对 10000007 取模之 后的结果。 输入输入输入文件名为 kpair.in，共 N+1 行。 第 1 行包含 2 个整数 N 和 K，表示序列的长度和逆序对的阶数。 接下来 N 行，每行一个整数，表示 Tim 给出的序列。第 i+1 行表示序列的第 i 个数。iA输出输出 输出文件名为 kpair.out。共 1 行，包含一个

13、整数，表示 K 阶逆序对的个数。你只需要输 出这个数对 1000007 取模之后的结果。分析分析 有了上面楼兰图腾的铺垫，相信读者能很快想出这道题目的解法。 我们可以发现，这个 K 阶逆序对是由一个个相互连接的逆序对组成的，我们可以考虑从 递推的方向上解决这个问题。 设表示以数 j 为结尾的长度为 i 的逆序对的个数(我们这里先假定序列 A 里面的数,jif 不超过 N)。类似地： Njkkifjif1, 1,答案就是。 NiiKfans1,时间复杂度为 O(NKlbN)三、小结三、小结 1、树状数组有两种模式的应用： 模式一：对数组 a的某个元素作修改 O(lbN)，查询某个区间内所有元素的

14、和 O(lbN) 模式二：随时修改数组 a中某个区间的值 O(1)，查询某个元素的值 O(lbN) 2、树状数组具有程序简单、代码短、不易出错、易推广到多维。 以二维为例，用 ck1k2表示 ck1-(2t1)+1k2-(2t2)+1 + . + ck1k2的总和。 3、树状数组相比线段树的优势：空间复杂度略低，编程复杂度低，容易扩展到多维情 况。劣势：由于对其进行的运算有限制，树状数组的应用范围并不广泛。 总的来说，树状数组始终只是一种数据结构，而数据结构的出现就是为了辅助解题用 的。也就是说，我们在学习树状数组的过程中要注意它的应用方面。比如说优化一些动规 方程，优化贪心的时间复杂度等等。

15、 其实树状数组还有其他更加高级的应用，像多维树状数组。由于篇幅的限制，这里不 能一一介绍，有兴趣的读者可以发我的邮箱：。 下面提供另外几道树状数组的题目，以便读者可以练习： 1.URAL P1028 Stars2.TYVJ P1474 打鼹鼠打鼹鼠 3. PKU P1195 Mobile phones 4. PKU P2481 Cows 5. Vijos P1448 校门外的树校门外的树 6.PKU P2155 Matrix 7.USACO 2004 OPEN Moofest 8.ZJOI2003 密码机密码机 9.9.PKU P3321 Apple Tree 10.Ural P1090 In the army now