数据结构-划分树 详解

😊 | Powered By HeartFireY | Dividing Tree 📕 | 需要的前导知识：可持久化线段树(Persistent Segment Tree)(->主席树) 一、划分树 简介

划分树是一种用于解决区间第 K K K大的数据结构。相比于主席树，其常数、理解难度都较低。但划分树是紧贴"区间第 K K K大"定义的基于排序的数据结构，在解决此类问题上具有优异的性质，而对于其他问题则体现出局限性。

划分树定义为，它的每一个节点保存区间 [ l f t , r h t ] [lft,rht] [lft,rht]所有元素，元素顺序与原数组（输入）相同，但是，两个子树的元素为该节点所有元素排序后 ( r h t − l f t + 1 ) 2 \frac{(rht-lft+1)}{2} 2(rht−lft+1)​个进入左子树，其余的到右子树，同时维护一个 n u m num num域， n u m [ i ] num[i] num[i]表示 l f t → i lft \rightarrow i lft→i这个点有多少个进入了左子树。

划分树在时间上与快排十分接近，但是通过直接对原序列进行快排查询区间第 K K K大会改变元素的位置。因此每求一次就需要恢复一次原序列。

二、划分树 结构与操作详解 1.建树操作

在进行建树操作之前，我们首先通过图片来了解一下划分树的基本结构：

我们可以结合上图理解划分树的建树分配过程：实际上就是每次遍历序列，对当前元素和所在区间的中位数进行比较，如果大于区间中位数则放置在右侧，反之则放置在左侧。(如图所示：带有标记的结点都是经过判断需要进入左子树的结点)

由于每次是对区间进行二分操作，因此对于由 n n n个数据构成的原始数组，最终需要 log ⁡ n \log n logn层构成最终的划分树结构。这便是依次划分的过程。但需要注意的是：由于实际上并不是严格的小于等于就分到左边，否则就分到右边。

显然，对于寻找中位数的过程，我们不可能每一次都对每层进行排序，这样的复杂度是非常大的。这里要引入一个非常重要的结论：我们只需要一次排序即可，当我们要求 [ l , r ] [l, r] [l,r]的中位数，实际上就是整个区间排序完成后的 n u m [ m i d ] num[mid] num[mid]。

此外，我们还需要额外的两个数组 t r e e [ l o g ( N ) ] [ N ] tree[log(N)][N] tree[log(N)][N]和 t o l e f t [ l o g ( N ) ] [ N ] toleft[log(N)][N] toleft[log(N)][N]:

• tree[log(N)][N]主要存储树结构，也就是所有的值，空间复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)
• toleft[log(N)][N]主要存储每一层 1   i 1~i 1 i进入左子树的结点数量。注意，实际上这是一个前缀和。

对于建树的操作，我们需要额外注意：

1. 建树需要分层，层数(即二维数组的第一维)按照 log ⁡ n \log n logn进行计算；
2. 划分的标准是中位数；
3. 每次划分的数永远存在它的下一层，同节点上的每个元素保持原序列中的相对顺序。
4. 过程上采用中序建树，先建根节点再递归建左右子节点。

建树前的分析与准备工作结束，那么建树的具体过程如下：

1. 根据排序后的数组找到当前层的中位数，将未进行排序的序列按照下列规则进行排列：

   (假设中值唯一)小于中位数的进入左子树，大于中位数的进入右子树

   如果中值不唯一，我们需要采取特殊的处理办法：首先我们假设中值左侧的元素全部小于中值，即另一个变量 s u p p o s e = m i d − l e f t + 1 suppose = mid - left + 1 suppose=mid−left+1，如果当前的数小于中值，就要使 s u p p o s e − 1 suppose - 1 suppose−1。

   • 如果中值唯一，则 s u p p o s e suppose suppose最终值必为 1 1 1，否则不唯一。
   • 如果不唯一，即 s u p p o s e > 1 suppose > 1 suppose>1，就将中值划分到左子树，直到 s u p p o s e = 0 suppose = 0 suppose=0；如果仍有中值，则划分到右子树。

2. 对于每一个子区间，都采取 1 1 1中的策略进行递归划分，递归终止条件为左右区间相等(到达单元素)；

3. 在向左子树中加入数字的时候，我们还需要额外统计出区间 [ l ,   r ] [l,\ r] [l, r]中进入左子树的元素数量。

根据上述过程写写出代码：

int tree[L][N], toleft[L][N];
void build(int level, int l, int r){
    if (l == r) return;						//递归终止条件
    int mid = (l + r) >> 1;		
    int suppose = mid - l + 1;				//用于记录与中间值相等，且划分到左孩子的数个数，初始化为区间长度
    for (int i = l; i > m;
    for(int i = 1; i > tree[0][i];
        sorted[i] = tree[0][i];
    }
    sort(sorted + 1, sorted + 1 + n);
    build(0, 1, n);
    for(int i = 1; i > a >> b >> c;
        cout