"可持久化线段树" 在本题目的作用实际上是指"使用多个入口指针保存多个不同版本的线段树", 
 类似GitHub, 每个版本包含当前版本和之前的所有内容: 每新增一个点都建一颗新树,
 复制前一棵树并插入新元素所造成的修改. 
 实现上, 是在build的时候只建立树的骨架而不保存元素, 而对每一个点都做一次insert, 
 在插入新点的同时, 复制上一棵树, 再插入新点

由于从1个点插到n个点, 每次都是二分插入, 时间空间复杂度就都是
$$log1+log2+…+logn = log(n!) = O(nlogn)$$

PS: N个点离散化之后的范围上限自然还是N

而当前问题是求某个区间内的第k小数, 而在解决这个问题的时候, 我们用这个”可持久化线段树”实际上是在干这事情: 对从a[1]到a[n]这个序列保存n份排序好的bst:

1. $a1$自己单独一个bst
2. $a1和a2$ 一个bst
3. $a1, a2和a3$ 一个bst
4. …
5. $a1$到an一个bst

每一棵树, 都是复制一份前一棵树然后再插入一个当前的$a_i$一共会保存n个bst.

每次插入的新节点, 若不是插在”复制的上一棵树副本”的左子树, 就是插在右子树

在题目询问区间$[l, r]$中的第k小数的时候, 我们观察一下$BST_r$跟$BST_{l-1}$:

可以看出$BST_r$跟$BST_{l-1}$的区别就是多插入了中间那第$l$到第$r$个数, 一共$r-l+1$个元素

容易看出, 如果我们用$BST_r$的左子树上面的元素个数减去$BST_{l-1}$的左子树元素个数, 结果就会是这$r-l+1$个新元素里面插入到左子树上的元素个数(设为$x$), 显然, 这$x$个元素是肯定比这$r-l+1$个新元素里面插到右子树上的元素小的.

假设$x > k$, 那么我们可以继续对这两个左子树做二分, 找出$BST_r$的左左子树比$BST_{l-1}$的左左子树多出的元素个数, 以此类推, 就能二分找到第k大的元素了…

而当$x < k$的时候, 类似二分右子树即可.

代码:

#pragma GCC optimize(2)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100010;
int n, m;
int a[N];
vector<int> nums;

struct Node
{
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];  //N * 4 + NlogN

int root[N], idx;

int find(int x)
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// 对左右边界建立节点并编号, build是建立好骨架, 每个版本insert改不同数据
int build (int l, int r)
{
    int p = ++idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid+1, r);
    return p;
}

// l, r是要放入的坐标范围, x是要插入的数离散化后的位置
int insert(int p, int l, int r, int x)
{
    // 假设现在是从外界第一次执行insert, 那么调用的时候, p必定是根节点,
    // 那么q就相当于复制了一个根节点, 从节点q进入这棵树的时候, 也能得到之前的所有内容.
    // 同理, 再往下二分递归的时候, insert会继续复制根节点的左(右)子树, 一直递归直到l==r之前,
    // q和原来的p都是一毛一样. 直到l==r才真正插入了新点, 每次插入的时间空间复杂度都是lgk,
    // 总加起来就是lg1+lg2+...+lgn = lg(n!), 根据stirling公式, 结果为nlgn   (大O)
    int q = ++idx;
    tr[q] = tr[p]; 
    if (l == r)  // 如果区间长度为1, 说明就是放这里了
    {
        // tr[q].cnt++是表示插在这个叶节点上
        // 这个线段树只是保存的每个区间里面的元素个数
        // 每次插入都只是覆盖到的那堆区间里面的cnt发生+1
        tr[q].cnt++;
        return q;
    }

    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid+1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;  // 相当于pushup了
    return q;
}


// l ,r是检索范围, q是当前第r个节点root[r]能包含1~r之间所有
// p的输入是root[l-1], 作用是剔除这个根节点所包含数据的影响
int query(int q, int p, int l, int r, int k)
{
    if (l == r) return r; // 如果找到位置

    // 目标是求l r之间的第k小
    // tr[tr[q].l].cnt - tr[tr[p].l].cnt的结果是求出在p之后插入到q这些数之后,
    // 有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1]), 
    // 所以cnt就是相当于"存在q左子树里面但不存在于1, l 之间的数的个数"
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; 

    int mid = l + r >> 1;
    // k <= cnt说明要找的元素在q的左子树里面, 同时这里面也要剔除掉包含在p左子树的内容
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid+1, r, k - cnt);  // 类似同上
}


int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);  //离散化使用
    }

    // 离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    // 构造线段树, 构造n个版本的线段树
    // 第0个版本的什么都没有就用build, build是建立好骨架, 每个版本insert改不同数据
    root[0] = build(0, nums.size() - 1);
    // 后面的每插入一个点算一个版本, 每次插入都只是比上一个版本多1个数
    // 左右参数给0和nums.size()-1是因为离散化之后的值域就是在0, nums.size()-1之间
    // 要插入必须得把这些地方全包才能保证找得到插入点
    for (int i = 1; i <= n; i++)
        root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));


    while (m -- )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l-1], 0, nums.size()-1, k)]);
    }
    return 0;
}

划分树

$划分树主要是使用快排划分的思想, 统计某个区间内小于大于中位数的个数, 与k比较.$

$划分树算法分为两个步骤, 建树和查询:$
$建树的时候就是把快排的每一步都记下来, 并且记录每次划分划分到左边的元素的个数,$
$然后都用二维数组存起来即可.$
$这里我们使用比较low的从前往后扫描划分而不是y总的前后交换快排模板, 是为了维护一种关键性质:$
$”划分到同一边的元素,在上一层先出现的元素一定在后出现的元素前面”$

树结构定义:

int tree[20][N];  // 20是因为二分所以不超过lg100000层, 储存每一层结构
int toLeft[20][N];  // 储存当前区间应该划分到左边的元素个数
int sorted[N];  // 排序好的原数组, 用于快速获取每一小段中位数

$然后开始建树的时候, 我们考虑划分的边界问题:$
$中位数到底出现在哪边呢? 如果中位数有多个, 那么要怎么办呢?$
$答: 由于我们在实现上使用数组来存这个划分树, 那么就得使用mid来固定左右子树的边界,$ $所以左右子树分别的元素个数都是固定的. 而当遇到中位数的情况,$ $我们得判断”在确定能划分到左边的元素都放到左边之后, 还有几个位置是留给中位数的?”$
$这个数字可以通过扫描一遍整个数组来获得$

建树代码:

void build(int level, int l, int r) //level为当前层
{
    if (l == r) return;
    int mid = l + r >> 1;

    // 获取需要划到左子树的中位数个数
    int median_in_l = mid - l + 1;
    for (int i = l; i <= r; ++i)
        if (tree[level][i] < sorted[mid])
            --median_in_l;
    // 开始分划建树
    int i = l, j = mid + 1; //进入下层左右子树的起始下标
    for (int k = l; k <= r; ++k)
    {
        if (k != l) toLeft[level][k] = toLeft[level][k - 1]; // 初始化
        // 确定划分到左边
        if (tree[level][k] < sorted[mid])  
        {                                                
            tree[level + 1][i++] = tree[level][k]; //将数放在下一层
            toLeft[level][k]++;  
        }
        // 把median_in_l个中位数划分到左边
        else if (tree[level][k] == sorted[mid] && median_in_l > 0) 
        {
            tree[level + 1][i++] = tree[level][k];
            toLeft[level][k]++; 
            --median_in_l;
        }
        // 划分到右边
        else tree[level + 1][j++] = tree[level][k]; 
    }

    build(level + 1, l, mid);     
    build(level + 1, mid + 1, r);
}

在建好树之后，接下来就是查询的问题。
假设初始大区间为$[l , r]$，要查询的区间为$[ql , qr]$
现在的目标是要查询区间$[ql , qr]$的第k大数

$类似线段树, 我们在[l, r]里面递归查询[ql , qr] , 并且根据左右划分情况调整k即可.$

$然后我们使用toLeft数组来辅助.$
$在区间[l , ql )中有toLeft [ level ] [ ql - 1 ] 个元素进入了左子树，记它为lql，$
$同理，在区间[l , qr]中有toLeft [ level ] [ qr ] 个元素进入了左子树，$，
$所以在区间[ql , qr]之间就有toLeft[level][qr] - lql个元素进入了左子树，记为 qlrl。$
$如果 qlrl >= k ，说明第k大元素肯定进入了左子树，那么就进入左子树查找，否则进入右子树查找。$

PS:当然, 这样做是正确的前提, 是像上文写的我们是从左往右扫描划分的, 划分到同一边的元素, 在上一层先出现的元素一定在后出现的元素前

$那么接下来要解决确定在子树内要查询的区间：$
$如果进入的是左子树，那么查询区间就应该是$
$[ l +( [l, ql-1] )进入左子树的数目，l +（ [l, qr] ）进入左子树的数目-1]$
PS:上面的-1是元素个数到区间坐标转换-1
$即：[l + lql , left + toLeft[level][qr] - 1],并且，这时候k的值不用变化。$
$其中$
$( [ l, ql-1] )进入左子树的数目 就是要求的区间前面的数还留在左子树的元素个数$
$( [ l, qr])进入左子树的数目-1 就是要求的区间包括前面部分还留在左子树的元素个数而他们相减之后,$
$就是整个[ql, qr]还留在当前子树里面的元素个数$

$令mid = ( l + r ) / 2, 那么mid + 1就是右子树的起点$
$如果进入的是右子树，那么小区间就应该是$
$[mid + 1 + ( [l, ql - 1] )进入右子树的数目，mid +（ [ l, qr] ）进入右子树的数目]$
$即：[mid + 1 + (ql - l - lql) , mid + 1 + qr - l - toLeft[level][qr]]$
$同时，这里的k要发生变化，变为k-（[ql , qr]进入左子树的元素个数）$
$即 k- qlrl$
$其中$
$( [ l, ql-1] )进入右子树的数目 这些数都是右边子树里面与当前区间无关的, 所以要剔除掉这些才行,$ $mid+1加上这个就是新的区间起点$
$（ [ l , qr ] ）进入右子树的数目 是qr与之前范围留在右子树的元素总个数, 里面剔除掉( [ l,ql-1])$
$进入右子树的数目 , 就是[ql, qr]还留在当前子树里面的元素个数$
$然后我们求的k要改变因为要把跑去了左子树的值的数量去掉,$
$也就是k = k - （[ql , qr]进入左子树的元素个数）$

查询代码:

// [ql, qr]为查询的区间，[l,r]为原始区间
int query(int level, int ql, int qr, int l, int r, int k)
{
    if (ql == qr) return tree[level][ql];  //终止条件

    int mid = l + r >> 1;

    // lql 表示[l, ql]进入左子树的个数
    int lql = ql == l ? 0 : toLeft[level][ql - 1];
    // qlrl 表示[ql, qr]进入左子树的个数
    int qlrl = toLeft[level][qr] - lql; 

    if (k <= qlrl) //进入左子树
    {
        int newLeft = l + lql;
        int newRight = l + toLeft[level][qr] - 1;
        return query(level + 1, newLeft, newRight, l, mid, k);
    }
    else //进入右子树
    {
        // 这里的mid是根据当前l和r而改变的, 只是个相对值, 在原来树上作用的时候, 得加回来
        // ql - l 是区间左边和无关的元素个数, 减去lql([l,ql]进入左子树的个数)就是到了右子树的个数
        int newLeft = mid + 1 + ql - l - lql;
        // qr - l 是整个大区间元素个数
        // 减去lql([l,ql]进入左子树的个数)
        // 再减去qlrl [ql,qr]进入左子树的个数 
        // 结果就是[l, qr]进入到当前右子树的所有元素的个数
        // 而我们有newLeft里来把里面属于[l, ql-1]的数给先去掉
        // 所以最后得到的[newLeft, newRight] 就是新的区间
        int newRight = mid + 1 + qr - l - toLeft[level][qr];
        return query(level + 1, newLeft, newRight, mid + 1, r, k - qlrl);
    }
}
// 包一下好看点, 0起点都要处理下, 调用的时候直接q(l ,r, k)即可
int q(int l, int r, int k)
{
    return  query(0, l - 1, r - 1, 0, n - 1, k);
}

排序时间复杂度$O(nlogn)$
建树时间空间复杂度都是$O(nlogn)$
查询时间复杂度$O(logn)$, $m$次询问就是$O(mlogn)$;

ac代码:

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, m;

int tree[20][N];  // 20是因为二分所以不超过lg100000层, 储存每一层结构
int toLeft[20][N];  // 储存当前区间应该划分到左边的元素个数
int sorted[N];  // 排序好的原数组, 用于快速获取每一小段中位数


void build(int level, int l, int r) //level为当前层
{
    if (l == r) return;
    int mid = l + r >> 1;

    // 获取需要划到左子树的中位数个数
    int median_in_l = mid - l + 1;
    for (int i = l; i <= r; ++i)
        if (tree[level][i] < sorted[mid])
            --median_in_l;
    // 开始分划建树
    int i = l, j = mid + 1; //进入下层左右子树的起始下标
    for (int k = l; k <= r; ++k)
    {
        if (k != l) toLeft[level][k] = toLeft[level][k - 1]; // 初始化
        // 确定划分到左边
        if (tree[level][k] < sorted[mid])  
        {                                                
            tree[level + 1][i++] = tree[level][k]; //将数放在下一层
            toLeft[level][k]++;  
        }
        // 把median_in_l个中位数划分到左边
        else if (tree[level][k] == sorted[mid] && median_in_l > 0) 
        {
            tree[level + 1][i++] = tree[level][k];
            toLeft[level][k]++; 
            --median_in_l;
        }
        // 划分到右边
        else tree[level + 1][j++] = tree[level][k]; 
    }

    build(level + 1, l, mid);     
    build(level + 1, mid + 1, r);
}




// [ql, qr]为查询的区间，[l,r]为原始区间
int query(int level, int ql, int qr, int l, int r, int k)
{
    if (ql == qr) return tree[level][ql];  //终止条件

    int mid = l + r >> 1;

    // lql 表示[l, ql]进入左子树的个数
    int lql = ql == l ? 0 : toLeft[level][ql - 1];
    // qlrl 表示[ql, qr]进入左子树的个数
    int qlrl = toLeft[level][qr] - lql; 

    if (k <= qlrl) //进入左子树
    {
        int newLeft = l + lql;
        int newRight = l + toLeft[level][qr] - 1;
        return query(level + 1, newLeft, newRight, l, mid, k);
    }
    else //进入右子树
    {
        // 这里的mid是根据当前l和r而改变的, 只是个相对值, 在原来树上作用的时候, 得加回来
        // ql - l 是区间左边和无关的元素个数, 减去lql([l,ql]进入左子树的个数)就是到了右子树的个数
        int newLeft = mid + 1 + ql - l - lql;
        // qr - l 是整个大区间元素个数
        // 减去lql([l,ql]进入左子树的个数)
        // 再减去qlrl [ql,qr]进入左子树的个数 
        // 结果就是[l, qr]进入到当前右子树的所有元素的个数
        // 而我们有newLeft里来把里面属于[l, ql-1]的数给先去掉
        // 所以最后得到的[newLeft, newRight] 就是新的区间
        int newRight = mid + 1 + qr - l - toLeft[level][qr];
        return query(level + 1, newLeft, newRight, mid + 1, r, k - qlrl);
    }
}
// 包一下好看点, 调用的时候直接q(l ,r, k)即可
int q(int l, int r, int k)
{
    return  query(0, l - 1, r - 1, 0, n - 1, k);
}






int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &tree[0][i]);
        sorted[i] = tree[0][i];
    }

    sort(sorted, sorted + n);

    build(0, 0, n - 1);
    while (m -- )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", q(l, r, k));
    }
    return 0;
}

归并树

建树就是归并排序过程$O(nlogn)$
查询的时候$O(mlognlogn)$

算法流程解析晚点有空补

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, m;
int tr[20][N];
int a[N];
int tmp[N];

void build(int deep, int l, int r)
{ 
    if (l == r)
    {
        tr[deep][l] = a[l];
        return;
    }
    // 归并自下往上构造归并树
    int mid = (l + r) >> 1;
    build(deep + 1, l, mid), build(deep + 1, mid + 1, r); //先构造子节点
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (tr[deep + 1][i] <= tr[deep + 1][j]) tmp[k++] = tr[deep + 1][i++];
        else tmp[k++] = tr[deep + 1][j++];
    }

    while (i <= mid) tmp[k++] = tr[deep + 1][i++];
    while (j <= r) tmp[k++] = tr[deep + 1][j++];

    for (i = l, k = 0; i <= r; ++i, ++k) tr[deep][i] = tmp[k];
}


// 计算[L,R]交[l,r]中小于x的有多少个数
int calc(int deep, int L, int R, int l, int r, int x)
{ 
    //[L,R]完全被[l,r]包含,直接二分查找返回
    if (L >= l && R <= r) return lower_bound(tr[deep] + L, tr[deep] + R + 1, x) - tr[deep] - L;
    int mid = (L + R) >> 1, ans = 0; //否则到子节点查找
    if (mid >= l) ans += calc(deep + 1, L, mid, l, r, x);
    if (mid < r) ans += calc(deep + 1, mid + 1, R, l, r, x);
    return ans;
}


int query(int l, int r, int k)
{
    int L = 0, R = n - 1;
    // 二分找右端点
    while (L < R)
    { 
        int mid = L + R + 1 >> 1;
        int cnt = calc(0, 0, n - 1, l, r, tr[0][mid]);
        // printf("L: %d, R: %d, mid: %d, tr[0][mid]: %d, cnt: %d\n", L, R, mid, tr[0][mid], cnt);
        if (cnt <= k) L = mid;
        else R = mid - 1;
    }
    return tr[0][L];
}



int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    build(0, 0, n - 1);

    while (m -- )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(l - 1, r - 1, k - 1));
    }
    return 0;
}