本节书摘来自华章计算机《程序设计解题策略》一书中的第1章，第1.1节,作者：吴永辉　王建德 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

第1章　利用树型数据关系的解题策略　

树是一个具有层次结构的集合，一种限制前件数且没有回路的连通图。在现实生活和程序设计的竞赛试题中，许多问题的数据关系呈树型结构，因此有关树的概念、原理、操作方法和一些由树的数据结构支持的算法，一直受到编程者的重视，被广泛应用于解题过程。在本章里，我们将介绍利用树型数据关系解题的七种策略：

1) 利用划分树求解整数区间内第k大值。2) 利用最小生成树及其扩展形式(最优比率生成树、最小k度生成树、次小生成树)计算有权连通无向图中边权和满足限制条件的最优生成树。3) 利用线段树计算区间。4) 利用改进型的二叉查找树(伸展树和红黑树)优化动态集合的操作。5) 利用动态树维护森林的连通性。6) 利用左偏树实现优先队列的合并。7) 利用跳跃表取代树结构，这种策略不失时空效率，容易编程实现。前六种树型结构鲜见于一般数据结构教材，利用这些特殊类型的树可优化存储结构和算法效率。

1.1　利用划分树求解整数区间内第k大的值

如何快速求出(在log2n的时间复杂度内)整数区间［x，y］中第k大的值(x≤k≤y)？注意，所谓区间指的是整数的序号范围，［x，y］指区间内第x个整数至第y个整数间的y-x+1个整数，而不是指整数值本身。

人们通常会想到采用快速查找法查找整数区间的第k大值，但这种方法会破坏原序列且需要O(n)的时间复杂度，即便使用平衡二叉树进行维护，虽每次查找时间复杂度降为O(log2n)，但由于丢失了原序列的顺序信息，也很难查找出某区间内的第k大值。划分树主要是针对上述问题而设计的。划分树是一种基于线段树的数据结构，其基本思想就是将待查找区间划分成两个子区间：不大于数列中间值的元素被分配到左儿子的子区间，简称左子区间；大于数列中间值的元素被分配到右儿子的子区间，简称右子区间。显然，左子区间的数小于右子区间的数。建树的时候要注意，对于被分到同一子树的元素，元素间的相对位置不能改变。例如构建整数序列［1 5 2 3 6 4 7 3 0 0］的划分树：整数序列经排序后得到［0 0 1 2 3 4 5 6 7］，中间值为3。划分出下一层的左子区间［1 2 3 0 0］，中间值为1；下一层的由子区间［5 6 4 7 3］，中间值为5；以中间值为界，划分出当前层每个区间的下层左右子区间……依此类推，直至划分出的所有子区间含单个整数为止(见图1.1-1)。由图1.1-1可见，划分树是一棵完全二叉树，树叶为单元素区间。若数列含n个整数，则对应的划分树有「log2n+1层。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，直至查找范围缩小到单元素区间为止。此时，区间内的第k大值就找到了。整个算法分两步：1) 建树——离线构建整个查询区间的划分树。2) 查找——在划分树中查找某个子区间中第k大值。

1.1.1　离线构建整个查询区间的划分树

在查询之前，我们先离线构建整个查询区间的划分树。建树过程比较简单，对于区间［l，r］，首先通过对原数列排序找到这个区间的中间值的位置midmid=l+r2」，不大于中间值的数划入左子树［l，mid］，大于中间值的数划入右子树［mid+1，r］。同时，对于第i个数，记录在［l，i］区间内有多少整数被划入左子树。然后继续对它的左子树区间［l，mid］和右子树区间［mid+1，r］递归建树，直至划分出最后一层的叶节点为止，显然，建树过程是自上而下的。具体实现办法：先将读入的数据排序成sorted［］，取区间［l，r］的中间值sorted［mid］mid=l+r2」，然后扫描［l，r］区间，依次将每个整数划分到左子区间［l，mid］或右子区间［mid+1，r］中去。注意，被分到每个子树的整数是相对有序的，即对于被分到每一棵子树里面的数，不改变它们以前的相对顺序。另外，在进行这个过程的时候，记录一个类似前缀和的东西，即l到i这个区间内有多少整数被划分到左子树。设：tree［p］［i］——第p层中第i位置的整数值，初始序列为tree［0］［］。sorted［］——排序序列，即存储tree［0］［］排序后的结果。toleft［］［］——toleft［p］［i］表示第p层前i个数里中有多少个整数分入下一层的左子区间。lpos和rpos——下一层左子区间和右子区间的指针。same——当前区间等于中间值的整数个数。下面给出实现建树的具体代码。

void build(int l,int r,int dep)　　　　　　　　　　　// 从dep层的区间［l,r］出发，自上而下构建划分树{if(l==r)return;// 若划分至叶子，则回溯int mid=(l+r)>>1;// 计算区间的中间指针int same=mid-l+1;// 计算［l,r］的中间值被分入下层后左子区间的// 个数samefor(int i=l;i<=r;i++) if(tree［dep］［i］
    
     0){ tree［dep+1］［lpos++］=tree［dep］［i］;same--; }else tree［dep+1］［rpos++］=tree［dep］［i］;toleft［dep］［i］=toleft［dep］［l-1］+lpos-l;// 计算dep层的第1个数到第i个数放入下一层// 左子区间的个数}build(l,mid,dep+1);// 递归计算下一层的左子区间build(mid+1,r,dep+1);// 递归计算下一层的右子区间}
    

1.1.2　在划分树上查询子区间［l，r］中第k大的数

如何在大区间［L，R］里查询子区间［l，r］中第k大的数呢(L≤l，r≤R)？我们从划分树的根出发，自上而下查找：若查询至叶子(l==r)，则该整数(tree［dep］［l］)为子区间［l，r］中第k大的数；否则区间［L，l-1］内有toleft［dep］［l-1］个整数进入下一层的左子树，区间［L，r］内有toleft［dep］［r］个整数进入下层的左子树。显然，在查询子区间［l，r］中有cnt=toleft［dep］［r］-toleft［dep］［l-1］个整数进入了下一层的左子树。如果cnt≥k，则递归查询左子树(对应区间［L，mid］)；否则递归查询右子树(对应区间［mid+1，R］)。难点是，如何在对应子树的大区间中计算被查询的子区间［newl，newr］？若递归查询左子树，则当前子区间的左边是上一层区间［L，l-1］里的toleft［dep］［l-1］-toleft［dep］［L-1］个整数，由此得到newl=L+toleft［dep］［l-1］-toleft［dep］［L-1］；加上上一层查询区间［l，r］中的cnt个整数，newr=newl+cnt-1(这里-1是为了处理边界问题，值得大家认真思索)，即在大区间［L，mid］里查询子区间［newl，newr］中第k大的值。同理，若递归查询右子树，则［l，r］中有r-l-cnt个整数进入右子树，需要计算其中第k-cnt大的整数值。关键是如何计算被查询子区间的右指针newr：当上一层的［l，r］和［r+1，R］中有若干个整数被分配至下一层左子区间，其中［r+1，R］中有toleft［dep］［R］-toleft［dep］［r］个整数位于左子区间右方(保持相对顺序不变)，因此查询子区间的右指针移至r右方的第toleft［dep］［R］-toleft［dep］［r］个位置，即newr=r+toleft［dep］［R］-toleft［dep］［r］。显然，左指针newl=newr-(r-l-cnt)。下面给出实现查询的具体代码。int query(int L,int R,int l,int r,int dep,int k)// `javascript从划分树的dep层出发，自上而下在大区间// ［L,R］里查询子区间［l,r］中第k大的数{ if(l==r)return tree［dep］［l］;// 若查询至叶子，则该整数为子区间［l,r］中// 第k大的数int mid=(L+R)>>1;// 取大区间的中间指针int cnt=toleft［dep］［r］-toleft［dep］［l-1］;// 计算［l,r］中被划入下一层左子区间的整数个数if(cnt>=k)// 递归查询左子树，对应的大区间为［L,mid］，// 小区间为［newl,newr］，计算其中第k大的值int newl=L+toleft［dep］［l-1］-toleft［dep］［L-1］;int newr=newl+cnt-1;return query(L,mid,newl,newr,dep+1,k);}Else// 递归查询右子树，对应的大区间为［mid+1,R］，// 小区间为［newl,newr］，计算其中第k-cnt大的值{ int newr=r+toleft［dep］［R］-toleft［dep］［r］;int newl=newr-(r-l-cnt);return query(mid+1,R,newl,newr,dep+1,k-cnt);}}

**1.1.3　应用划分树解题**虽然划分树是一种基于线段树的数据结构，但被分到同一子树的元素间的相对位置不改变，因此将其用于查询子区间［l，r］中第k大的值是十分适合的。【1.1.1　K-th Number】【问题描述】您为Macrohard公司的数据结构部门工作，现在被要求编写一个新的数据结构，该数据结构能在一个数组段中快速地返回第k个次序统计数据。也就是说，给出一个数组a［1..n］，包含了不同的整数，程序要回答一系列这样形式的问题Q(i，j，k)：“在数组a［i..j］段中第k个数是什么，如果这一段是排好序的？”例如，数组a=(1，5，2，6，3，7，4)，问题是Q(2，5，3)，数组段a［2..5］是(5，2，6，3)。如果对这一段进行排序，得(2，3，5，6)，第3个数是5，所以这个问题的答案是5。输入：输入的第一行给出数组的大小n和要回答的问题数m(1≤n≤100000，1≤m≤5000)。第二行给出回答问题的数组，即n个不同绝对值不超过109的整数。后面的m行给出问题描述，每个问题由3个整数组成：i、j和k(1≤i≤j≤n，1≤k≤j-i+1)，表示相应的问题Q(i，j，k)。输出：对每个问题输出答案——在已排好序的a［i..j］段输出第k个数。
    
 
     
    
提示：本题海量输入，采用C风格输入-输出(scanf，printf)，否则超时。试题来源：ACM Northeastern Europe 2004，Northern Subregion在线测试地址：POJ 2104试题解析简述题意：给出一个长度为n的整数序列，要求你反复采用快速查找方法查找某个子序列中第k大的值。显然，采用划分树查询是最高效的。方法是：1) 先离线构建整数序列的划分树(排序整数序列，调用过程build(1，n，0))。2) 反复输入查询(a，b，c)，通过调用函数query(1，n，a，b，0，c)计算和输出［a，b］区间中第c大的值。程序清单

include

include

include

include

using namespace std;

const int MAXN=100010;// 整数序列规模大小的上限int tree［30］［MAXN］;// tree［p］［i］表示第p层中第i位置的值int sorted［MAXN］;// 已经排序的数int toleft［30］［MAXN］;// toleft［p］［i］表示第p层从1到i中有多少// 个数被划入下一层的左子区间构建划分树的过程build(l，r，deep)和查询函数query(L，R，l，r，deep，k)如前所述，这里不再赘述。下面，分别给出输入整型数的外挂函数和主程序。static inline int Rint()// Rint()为整型数输入函数。函数返回类型前// 加上关键字inline即把Rint()指定为内联{ struct X{ int dig［256］;// 标志有用码X(){ for(int i='0';i<='9';++i) dig［i］=1;dig［'-'］=1;}};static　X fuck;int s=1， v=0，c;// 假定正数，整数值初始化为0for (; !fuck.dig［c=getchar()］;);// 输入忽略串首的无用码if (c=='-') s=0;// 设负数标志else if (fuck.dig［c］)v=c^48;// 记录最高位的数值for(;fuck.dig［c=getchar()］;v=v*10+(c^48));// 按照由高位至低位的顺序输入数码并计算整// 数值vreturn s ？ v :-v;// 返回整数值}

int main()// 主程序

{ int n，m;while(～scanf("%d %d"，&n，&m))// 反复输入数组的大小和要回答的问题数{ for(int i=1;i<=n; i++)// 输入数组，排序数组初始化{ scanf("%d"，&tree［0］［i］);sorted［i］=tree［0］［i］;}sort(sorted+1，sorted+n+1);// 计算排序数组sorted［］build(1，n，0);// 从0层的根节点1出发，建立区间［1，n］的划分树while(m--)// 依次和处理m个询问{ int a，b，c;scanf("%d %d %d"，&a，&b，&c);// 输入当前询问printf("%d＼n"， query(1，n，a，b，0，c));// 计算和输出［1，n］的子区间［a，b］中第c大的值}}return 0;}

在一些较复杂的综合题中，划分树经常被作为核心子程序，与其他算法配合使用。【1.1.2　Super Mario】【问题描述】Mario是世界著名的水管工。他的“魁梧”体格和惊人的弹跳能力经常让我们想起他。现在可怜的公主又有麻烦了，Mario要去拯救他的情人。我们把到老板城堡路作为直线(其长度为n)，在每个整数点i、高度hi的地方有一块砖。现在的问题是，如果Mario能跳的最大高度为h，在［L，R］区间内要有多少块砖，Mario才可以踩踏上去。输入：第一行给出整数T，表示测试用例的数目。对每个测试用例：第一行给出两个整数n、m(1≤n≤10^5，1≤m≤10^5)，n是路的长度，m是查询次数。下一行给出n个整数，表示每块砖的高度，范围是［0，1000000000］。接下来的m行，每行给出3个整数L、R、h。(0≤L≤R
     
     试题来源：2012 ACM/ICPC Asia Regional Hangzhou Online在线测试地址：HDOJ 4417试题解析简述题意：查询区间［L，R］内不大于H的数字个数，即在Mario最大跳跃高度为H的情况下，他在［L，R］内可踩踏多少块砖。本题是一道综合题，采用的算法是二分查找+划分树：若Mario能够跳过高度为x的砖头，则所有高度不大于x的砖头都能够跳过。这就凸显出问题的单调性，使得二分查找方法得以施展。我们将区间［s，t］映射成大小值区间=［l，r］=［1，(t-s)+1］，每次计算中间指针mid=l+r2」，采用划分树计算区间［s，t］的中间值(即区间［s，t］中第mid大砖头的高度)，并询问该值是否不大于Mario跳跃的最大高度h：若是，则说明Mario能够跳过的砖头数至少为mid，记下，并搜索右子区间［mid+1，t］，尝试计算能跳过的更多砖头数；否则说明Mario不能够跳过mid块砖头，因此在左子区间［s，mid-1］中搜索能够跳过的砖头数。这个过程一直进行至区间不存在为止。此时记录下的砖头数即为问题的解。程序清单
    

include

include

include

include

using namespace std;

const int MAXN=100010;　　　　　　　　　// 路长上限int tree［30］［MAXN］;// tree［p］［i］表示第p层中第i位置的值int sorted［MAXN］;// 已经排序的数int toleft［30］［MAXN］;// toleft［p］［i］表示第p层从1到i中有多少个数被划入// 下一层的左子区间构建划分树的过程build(l，r，deep)和查询函数query(L，R，l，r，deep，k)如前所述，这里不再赘述。int solve(int n,int s,int t,int h)// Mario跳跃的最大高度为h时能够跳过区间［s，t］中的砖头数{ int ans=0;// 能够跳过的砖头数初始时为0int l=1;// 区间［s.t］映射成序号区间［l,r］int r=(t-s)+1;int mid;while(l<=r)// 二分查找Mario能够跳过区间［s,t］中的砖头数{ mid=(l+r)>>1;// 计算中间指针int temp=query(1,n,s,t,0,mid);// 在区间［s,t］中查询第mid大的值if(temp<=h)// 若该值不大于Mario能跳的最大高度h，则设定Mario能够// 跳过区间［s,t］中的mid块砖头，继续搜索右子区间{ ans=mid;l=mid+1;}else r=mid-1;// 否则搜索左子区间}return ans;// 返回问题解}

int main()

{ int T;int n,m;int s,t,h;scanf("%d",&T);// 输入测试用例数int iCase=0;// 测试用例编号初始化while(T--){ iCase++;scanf("%d%d",&n,&m);// 输入路长和查询次数memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++)// 输入每块砖的高度{ scanf("%d",&tree［0］［i］);sorted［i］=tree［0］［i］;// 排序序列初始化}sort(sorted+1,sorted+n+1);// 排序build(1,n,0);// 离线计算划分树printf("Case %d:＼n",iCase);// 输出测试用例编号while(m--){ scanf("%d%d%d",&s,&t,&h);// 输入当前询问s++;// 区间以1为基准t++;printf("%d＼n",solve(n,s,t,h));// 计算和输出Mario跳跃的最大高度为h时能够跳过区间// ［s,t］中的砖头数}}return 0;}