《利用树状数组解决几类问题.doc》由会员分享，可在线阅读，更多相关《利用树状数组解决几类问题.doc（9页珍藏版）》请在三一办公上搜索。
1、利用树状数组解决几类问题 树状数组作为一种实现简单、应用较广的高级数据结构，在OI界的地位越来越重要，下面我来简单介绍一下树状数组和它的简单应用。一、树状数组简介 树状数组(Binary Indexed Trees，简称BIT)是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。它可以方便地查询出一段区间中的数字之和。其查询和修改的时间复杂度均为O(lbN),并且是一个在线的数据结构，可以随时修改并查询。我接下来用一道题目来介绍树状数组的几个基本操作。【引例】假设有一列数Ai（1=i=n），支持如下两种操作：1. 将Ak的值加D。（k，D是输入的数）2. 输出（s
2、，t都是输入的数，s8 由此得出，c3、c4、c8亦应该添加x。定理的证明如下：【引 理】若Ak所牵动的序列为Cp1，Cp2 Cpm，且p1 p2pm，则有l1 l2lm（li为pi在二进制中末尾的个数）。证明：若存在某个i有lili+1，则，即： (1)而由Li=Li+1、Pi Pi+1可得 (2)(1) (2)矛盾，可知l1 l2 lm 定理2：p1=k，而p i+1=pi+2li证明：因为p1 p2 li的数（若出现Pi+x比pi+1更小，则x2li ，与x在二进制中的位数小于li相矛盾）。Pi+1=pi+2li，li+1li+1。由pi-2li+1KPi可知，Pi+1-2li+1+1P
3、i+2li2*2li+1=Pi 2li+1KPiP i+1 ，故Pi与pi+1之间的递推关系式为P i+1=Pi+2li【操作3】求数列的前n项和。只需找到n以前的所有最大子树，把其根节点的C加起来即可。不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,因此，求和操作的复杂度也是O(lbN)。根据ck=ak-2l+1+ +ak (l为k在二进制数中末尾的个数)，我们从k1=k出发，按：ki+1=ki-2lki（lki为ki在二进制数中末尾0的个数）递推k2，k3，km (km+1=0)。由此得出S=ck1+ck2+ck3 + + ckm相信看了这两个操作的理
4、论部分，读者应该有了一定的理解，下面给出这两种操作和其他一些重要操作的Pascal代码。【操作1】低位技术：Lowbit(k) Lowbit(k)：即k在2进制数中从最低位开始连续0的位数的关于2的幂。代码Function Lowbit(k:Longint) :Longint;BeginLowbit:=k and k;End;【操作2】修改操作：Modify(k, D) Modify(k, D)：对数组 a 中的第k个元素加上D。为了维护 C 数组，我就必须要把 C 中所有“管”着 ak 的 ck 全部加上D，这样才能随时以 O(lbN) 的复杂度进行 Sum(i) 的操作。而 k:=k+ L
5、owbit(k) 正是依次访问所有包含 ak 的 ck 的过程。修改ak，我们需对ck , ck+Lowbit(k) , ck+Lowbit(k)+Lowbit(k+Lowbit(k)进行修改。时间复杂度O(lbN) 。代码Procedure Modify(k,D:Longint);BeginWhile k0 Do Begin Sum:=CN+Sum; N:=N-Lowbit(N); End;End; 和其他高级数据结构一样，树状数组也支持求第k小元素、删除以及插入操作（这些一直不被人熟知)，下面我来重点介绍一下：【操作4】删除操作：Delete(k) 我们设Ci表示数i出现的次数，删除第k个
6、数只需要Dec(CAk)即可（如果Ak很大，只需要离散化即可）。代码Procedure Delete(K:Longint);BeginModify(Ak,-1);End;【操作5】插入操作：Insert(k)类似地，我们设Ci表示数i出现的次数，插入第k个数只需要Inc(CAk)即可（如果Ak很大，只需要离散化即可）。代码Procedure Insert(K:Longint);Begin Add(Ak,1);End;【操作6】取第K小的数：FindKth(K) 同操作4，我们设Ci表示数i出现的次数。如果要求出最小值，也就是说我们需要找出一个最小的i，使得，这个i必定是最小值。接下来就是如何找
7、出这个i的问题了。令，我们可以发现S具有单调性，于是我们可以通过二分查找来找出这个i.代码Function FindKth(K:Longint):Longint;Var Left,Right,Mid,tmp:Longint;Begin Left:=1; Right:=MaxValue; While Left=Right Do Begin Mid:=(Left+Right) shr 1; tmp:=Sum(mid); If tmpK Then Left:=Mid+1 elseBeginFindKth:=Mid;Right:=Mid-1;End;End;End; 以上三个操作的时间复杂度分别为：O
8、(lbN)、O(lbN)和O(lb2N)。其实用树状数组找第K小的数还有其他的做法，可以将时间复杂强度降为O(lbN)，这里就不再详细介绍，又想去的读者可以参见相关资料。二、利用树状数组解决几类问题1.区间求和类问题【例1】数列操作1描述给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和。输入输入数据第一行包含2个整数N，M（1N,M100000），表示序列的长度和操作的次数。接下来M行，每行会出现如下的一种格式： Add i x 将序列中第i个数加上x Sub i x 将序列中第i个数减去x Mul
9、 i x 将序列中第i个数乘上x Query i j 求出序列中第i个数到第j个数的和输出 对于每一个Query操作输出一个数，表示序列中第i个数到第j个数的和。分析：这道题目我们很容易想到用朴素模拟来解决，但时间复杂度最坏为O(NM)，超时是必然的。这时候我们就可以巧妙借助树状数组来解决这个问题。加、减与求和操作就如同上文介绍的一样简单，只与乘操作，我们可以先将这个数减至0，然后加上这个数乘以x。时间复杂度为O(MlbN)【例2】数列操作2描述给定一个初始值都为0的序列,动态地修改一段连续位置上的数字,加上一个数,减去一个数,然后动态地提出问题,问题的形式是求出一个位置的数字。输入输入数据第
10、一行包含2个整数N，M（1N,M100000），表示序列的长度和操作的次数。接下来M行，每行会出现如下的一种格式： Add i j x 将序列中第i个数到第j个数加上x Query i 求出序列中第i个数输出 对于每一个Query操作输出一个数，表示序列中第i个数。分析：我们把支持这种操作的树状数组称为树状数组的模式二，对于模式二，树状数组可以做到随时修改数组a中某个区间的值O(1)，查询某个元素的值O(lbN)在这种模式下，ai已经不再表示真实的值了，只不过是一个没有意义的、用来辅助的数组。这时我们真正需要的是另一个假想的数组b，bi 才表示真实的元素值。但 c 数组却始终是为a数组服务的，
11、这一点大家要明确。此时Sum(i)虽然也是求ai之前的元素和，但它现在表示的是实际我要的值，也就是 bi。比如现在我要对图1 中a数组中红色区域的值全部1。当然你可以用模式一的 Modify(i)对该区间内的每一个元素都修改一次，但如果这个区间很大，那么每次修改的复杂度就都是O(NlbN)，m次修改就是O(MNlbN)，这在M和N很大的时候仍是不满足要求的。这时模式二便派上了用场。我只要将该区域的第一个元素+1，最后一个元素的下一位置-1，对每个位置Sum(i)以后的值见图2：相信大家已经看得很清楚了，数组b正是我们想要的结果。模式二难理解主要在于 a 数组的意义。这时请不要再管ai表示什么，
12、ai已经没有意义了，我们需要的是bi！但模式二同样存在一个缺陷，如果要对某个区间内的元素求和，复杂度就变成O(nlbn) 了。所以要分清两种模式的优缺点，根据题目的条件选择合适的模式，灵活应变！【例3】SDOI2009HH的项链描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。输入第一行：一个整数N，表示项链的长
13、度。第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。第三行：一个整数M，表示HH询问的个数。接下来M行：每行两个整数，L和R（1 L R N），表示询问的区间。输出M行，每行一个整数，依次表示询问对应的答案。分析：本题数据规模较大，需要合理使用数据结构。题目中有两个元素：区间和颜色。如果直接使用线段树套平衡树，需要牵扯到“合并”操作，时间复杂度很高（比如当询问类似2,N-1的时候）。因此，需要做一些预处理工作使得询问更容易解决。观察在某一区间内出现的某种颜色，假设有若干个同色点都在这个区间中，而该颜色只能计算一遍，因此我们需要找出一个有“代表性”的点，当然
14、是第一个最有“代表性”。观察该点，以及它前后同色点的位置，有什么可以利用的规律？很显然，它的上一个同色点肯定在区间左侧，而同区间内的该颜色的其他点，它们的上一个同色点显然在区间内。这样，我们的工作便是找到询问区间l,r中这样的点x的个数：点x的上一个同色点在询问区间l,r左侧。到这一步，我们有一个在线算法：建线段树，将询问分成O(lbN)个小区间分别处理。如果再套平衡树，需要二分查找才能求符合条件的点的“个数”。这样总的理论最坏复杂度为O(M(lbN)3)，虽然实际情况会好一些，但还是难以符合要求。我们分析一下该算法复杂度高的原因：平衡树难以很好支持求“个数”的运算，需要二分来实现。那么求“个
15、数”效率最高的是什么数据结构？当然是树状数组。当然，线段树是无法再套树状数组的，那样空间复杂度会达到O(N2)，所以我们要舍弃线段树，寻找新的算法。对于一堆“无序”的询问区间，如果没有线段树，便很难处理。因此我们考虑将区间按左端点排序，使其有序，然后从左到右扫描每个点。再考虑那些“上一个同色点在询问区间左侧”的点，我们的目的是快速求出该区间中这种点的个数。而这些点的上一个同色点因为在询问区间左侧，所以已经被扫描过，而区间内其他点却没有！这样，如果我们换个角度，改“上一个”为“下一个”，预处理出每个点i的下一个同色点的位置Nexti，并且在扫描过该点i后使树状数组CNexti=1。那么对于询问区
16、间l,r，答案便是Sumcr-Sumcl-1！这样，算法只有“加1”和“求和”两种操作。问题到此得到圆满解决， 最终时间复杂度为O(MlbN)。 2.求序列中第k大数【例4】魔兽争霸描述小x正在销魂地玩魔兽他正控制着死亡骑士和N个食尸鬼(编号1N)去打猎。死亡骑士有个魔法，叫做“死亡缠绕”，可以给食尸鬼补充HP。战斗过程中敌人会对食尸鬼实施攻击，食尸鬼的HP会减少。小x希望随时知道自己部队的情况，即HP 值第k多的食尸鬼有多少HP，以便决定如何施放魔法。请同学们帮助他:)小x向你发出3种信号：（下划线在输入数据中表现为空格） A i a 表示敌军向第i 个食尸鬼发出了攻击，并使第i 个食尸鬼损
17、失了a 点HP，如果它的HP=0,那么这个食尸鬼就死了(Undead也是要死的)。敌军不会攻击一个已死的食尸鬼。 C i a 表示死亡骑士向第i个食尸鬼放出了死亡缠绕，并使其增加了a点HP。HP值没有上限。死亡骑士不会向一个已死的食尸鬼发出死亡缠绕 Q k 表示小x向你发出询问输入第一行，一个正整数N，以后N个整数 表示N个食尸鬼的初始HP 值接着一个正整数M，以下M行 每行一个小x发出的信号输出对于小x的每个询问，输出HP 第k多的食尸鬼有多少HP，如果食尸鬼总数不足k个，输出-1。每个一行数。最后一行输出一个数：战斗结束后剩余的食尸鬼分析 这道题目描述十分清楚，关键就是选取好的数据结构来实
18、现。 我们设Ci表示HP等于i出现的次数，假设所有数不超过S。 对于操作A_i_a：我们只需要将Chpi减1，Chpi-a加1即可，同时将hpi减a。要特殊考虑hpi-a小于等于0的情况； 对于操作C_i_a：我们只需要将Chpi减1，Chpi+a加1即可，同时将hpi加a； 对于操作Q_k：我们需要找到一个数x使得Ci=k |i=x,Cx0即可。 我们可以发现前两个操作的时间复杂度均为O(1)，而第三个操作的时间复杂度接近于O(S)。显然我们只要将操作3的时间复杂度降下来就可以了。注意到这道题目只需要求和，这时候树状数组就派上了巨大的用场。构建一个树状数组C： 对于操作A_i_a：我们只需要
19、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中的一个逆序对。例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(
20、5,2)，共4个。给定一个数组，求该数组中包含多少个逆序对。输入输入数据第一行包含一个整数N，表示数组的长度；第二行包含N个整数。输出输出数据只包含一个整数，表示逆序对的个数。分析如题，这道题目只要求输出逆序对的个数就可以了，传统的求逆序对的方法有好多，这里我只介绍用树状数组求逆序对。设Ci(i如果会很大，只需要离散化即可)表示i出现的次数。我们顺序枚举每一个数Ai，显然以Ai为结尾的逆序对的个数为，这一步我们可以利用树状数组优化到O(lbN)，接下来inc(CAi)。将所有的加起来就可以计算出答案了。【例6】TYVJ P1432楼兰图腾描述在完成了分配任务之后，西部314来到了楼兰古城的西部
21、。相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹()，他们分别用V和的形状来代表各自部落的图腾。西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),(n,yn),其中y1yn是1到N的一个排列。如图，图中的y1=5,y2=1,y3=2,y4=4,y5=3.西部314打算研究这幅壁画中包含着多少个图腾，其中V图腾的定义如下（注意：图腾的形式只和这三个纵坐标的相对大小排列
22、顺序有关）1=ijkyj,yjyk;而崇拜的部落的图腾被定义为1=ijk=N且yiyk;西部314想知道，这N个点中两个部落图腾的数目。因此，你需要编写一个程序来求出V的个数和的个数。输入第一行一个数N；第二行是N个数，分别代表y1，y2yn输出两个数，中间用空格隔开，依次为V的个数和的个数分析我们可以发现，如果能统计出V图腾的个数，那么图腾的个数也可以利用类似的方法统计出来，这里我介绍两种方法来统计V图腾的个数。方法一：我们可以发现V图腾的前半部分具有逆序对的性质，因此我们可以利用类似的方法统计V图腾的个数。设f1,i表示数i出现的次数，f2,i表示以数i为结尾的“”图腾的个数，f3,i表示
23、以数i结尾的V图腾的个数。接下来我们顺序枚举Yi，然后就是f1.3的转移：最后的答案就是，用树状数组优化这个方程就可以将时间复杂度降为O(NlbN)。方法二：我们可以从另一个角度来考虑。我们仔细观察一下图形，V图腾要求两边的点的高度大于中间的点的高度。也就是说定下了中间的点之后，我们只需要分别统计这个点左边和右边比他高的点的个数就可以了（分别设为LS和RS）。根据乘法原理，以这个点为中间点的V图腾的个数就是LS*RS。显然我们的答案就是。至于计算RS和LS的过程中，我们只需要用树状数组来优化就可以了。在实际运行效果中，虽然两种方法的时间复杂度都是O(NlbN)，但方法一花的时间远超过方法二。这
24、就告诉我们，在平时做题目的时候，要多多注意分析各种算法的时空复杂度，尽量使算法完美。【例7】K阶逆序对(原创题)描述Jim是一位数列爱好者，他对于各种数列都有一定的研究。同时他对和数列有关的数也特别感兴趣，最近他开始研究逆序对。先给出逆序对的定义：对于一个包含N个正整数的数组A1.N，如果有iAj，则称为数组A中的一个逆序对。例如，数组3,1,4,5,2的逆序对有,，共4个。同许多牛人一样，Jim很快解决了求一个给定序列的逆序对个数的问题。但Jim并不满足这一点，他开始研究逆序对的推广形式：K阶逆序对。下面给出K阶逆序对的定义：对于一个包含N个正整数的数组A1.N，如果存在一个序列B1.K，有
25、1=B1B2BKAB2ABK，则称为数组A中的一个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个数。输出输出文件名为kpair.out。共1行，包含一个整数，表示K阶逆序对的个数。你只需要输出这
26、个数对1000007取模之后的结果。分析有了上面楼兰图腾的铺垫，相信读者能很快想出这道题目的解法。我们可以发现，这个K阶逆序对是由一个个相互连接的逆序对组成的，我们可以考虑从递推的方向上解决这个问题。设表示以数j为结尾的长度为i的逆序对的个数(我们这里先假定序列A里面的数不超过N)。类似地：答案就是。时间复杂度为O(NKlbN)三、小结1、树状数组有两种模式的应用：模式一：对数组a的某个元素作修改O(lbN)，查询某个区间内所有元素的和O(lbN)模式二：随时修改数组a中某个区间的值O(1)，查询某个元素的值O(lbN)2、树状数组具有程序简单、代码短、不易出错、易推广到多维。以二维为例，用c
27、k1k2表示ck1-(2t1)+1k2-(2t2)+1 + . + ck1k2的总和。3、树状数组相比线段树的优势：空间复杂度略低，编程复杂度低，容易扩展到多维情况。劣势：由于对其进行的运算有限制，树状数组的应用范围并不广泛。总的来说，树状数组始终只是一种数据结构，而数据结构的出现就是为了辅助解题用的。也就是说，我们在学习树状数组的过程中要注意它的应用方面。比如说优化一些动规方程，优化贪心的时间复杂度等等。其实树状数组还有其他更加高级的应用，像多维树状数组。由于篇幅的限制，这里不能一一介绍，有兴趣的读者可以发我的邮箱：lx894489107。下面提供另外几道树状数组的题目，以便读者可以练习：1.URAL P1028 Stars2.TYVJ P1474 打鼹鼠3. PKU P1195 Mobile phones4. PKU P2481 Cows5. Vijos P1448 校门外的树6.PKU P2155 Matrix7.USACO 2004 OPEN Moofest8.ZJOI2003 密码机9.PKU P3321 Apple Tree10.Ural P1090 In the army now
