第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］的中间值被分入下层后左子区间的
// 个数same
for(int i=l;i<=r;i++) if(tree［dep］［i］<sorted［mid］)same--;
int lpos=l;// 下一层左子区间和右子区间的指针初始化
int rpos=mid+1;
for(int i=l;i<=r;i++)// 搜索区间［l,r］中的每个数
{
if(tree［dep］［i］<sorted［mid］)// 若dep层的第i个数据比中间值小，则被划入
// 下一层的左子区间；若相同于中间值，被划入下一层的左子区间，中间值被分入下层后左子区间的个数-1；
// 若大于中间值，则被划入下一层的右子区间
tree［dep+1］［lpos++］=tree［dep］［i］;
else if(tree［dep］［i］==sorted［mid］&&same>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个数。
<div style="text-align: center">
<img src="https://yqfile.alicdn.com/67f615c123eaaed1fa36b8a35af640ed05e19cb7.png " >
</div>
提示：本题海量输入，采用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大的值。
程序清单
```javascript
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
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;// 假定正数，整数值初始化为0
for (; !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));// 按照由高位至低位的顺序输入数码并计算整
// 数值v
return 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<n，0≤h≤1000000000)。
输出：
对每个测试用例，输出“Case X:”(X是从1开始的测试用例的编号)，然后给出m行，每行给出一个整数。第i个整数是针对第i个查询，Mario可以踩踏上去的砖块的个数。
试题来源：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<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
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;// 能够跳过的砖头数初始时为0
int 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;
}