左偏树

视频讲解：https://www.bilibili.com/video/BV1Hz4y177gn/

洛谷P3377 可并堆1 https://www.luogu.com.cn/problem/P3377

1. 左偏树核心概念解释

• 距离（dis）：节点的dis是到最近「外节点」（无右孩子的节点）的路径长度，空节点dis=-1，非空节点dis=右孩子dis+1（左偏树的dis由右孩子决定，保证左偏性质）；

• 左偏性质：任意节点的左孩子dis ≥ 右孩子dis，确保树的左侧更“深”，合并时优先合并右子树，减少调整次数；

• 小根堆性质：堆顶是最小值，合并时始终让值更小的节点作为根。

2. 并查集的作用

• 左偏树的合并/删除操作需要快速找到堆的根节点，通过并查集+路径压缩，将找根的时间复杂度降到均摊O(α(n))（阿克曼函数，接近常数），是左偏树高效操作的关键。

3. 关键操作逻辑

• 合并操作：先找两个堆的根→判断是否同堆→合并后更新并查集；

• 删除堆顶：找到堆根→输出值→标记删除→合并左右子树→更新并查集（让原堆的节点指向新根）。

4. 边界处理

• 空堆合并直接返回非空堆；

• 已删除节点（v=-1）跳过操作，避免无效计算；

• 空节点dis=-1是左偏树的约定，保证dis计算的正确性（如dis[x] = dis[rc[x]] + 1，空右孩子时dis[x]=0）。

#include <bits/stdc++.h>
using namespace std;

// ===================== 常量与全局变量定义 =====================
const int N = 1e5 + 10;  // 节点最大数量（适配题目数据范围）
// 核心数组：左偏树节点属性
int v[N];    // v[x]：节点x存储的数值（堆的权值），-1表示该节点已被删除
int lc[N];   // lc[x]：节点x的左孩子索引（0表示无左孩子）
int rc[N];   // rc[x]：节点x的右孩子索引（0表示无右孩子）
int dis[N];  // dis[x]：节点x的「距离」—— 到最近的「外节点」（无右孩子的节点）的路径长度
             // 空节点（0）的dis定义为-1，非空节点dis = 右孩子dis + 1
// 并查集数组：维护每个节点所属堆的根节点（路径压缩，快速找根）
int fa[N];

// ===================== 并查集核心函数（路径压缩） =====================
// 功能：查找节点x所在堆的根节点，同时进行路径压缩（降低后续查找复杂度）
// 路径压缩：将查询路径上的所有节点直接指向根节点，后续查找只需O(1)
int find(int x)
{
    // 递归终止条件：x的父节点是自身 → x是根节点
    // 否则递归查找父节点，并将x的父节点直接更新为根（路径压缩）
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

// ===================== 左偏树核心合并函数 =====================
// 功能：合并两个左偏树（以x为根的堆 和 以y为根的堆），返回合并后的根节点
// 核心性质：维护小根堆（值小的节点在堆顶） + 左偏性质（左孩子dis ≥ 右孩子dis）
int merge(int x, int y)
{
    // 边界条件：若其中一个堆为空，直接返回另一个堆的根（空堆不影响合并）
    if (!x || !y) return x + y;

    // 步骤1：保证小根堆性质 —— 让值更小的节点作为合并后的根
    // 若x的值 > y的值 → 交换x和y；若值相等，选编号更小的节点为根（避免歧义）
    if (v[x] == v[y] ? x > y : v[x] > v[y]) swap(x, y);

    // 步骤2：递归合并x的右子树 和 y
    // 左偏树的核心优化：合并总是优先合并右子树（保证左偏性质，减少调整次数）
    rc[x] = merge(rc[x], y);

    // 步骤3：维护左偏性质 —— 左孩子的dis必须 ≥ 右孩子的dis
    // 若左孩子dis < 右孩子dis → 交换左右孩子
    if (dis[lc[x]] < dis[rc[x]]) swap(lc[x], rc[x]);

    // 步骤4：更新当前节点x的dis（dis定义为右孩子dis + 1）
    // 因为左偏树的dis由右孩子决定（右子树更浅，保证左偏）
    dis[x] = dis[rc[x]] + 1;

    // 返回合并后的根节点（x）
    return x;
}

// ===================== 主函数（处理输入输出 + 操作逻辑） =====================
int main()
{
    int n, m;  // n：初始元素个数（每个元素自成一个左偏树）；m：操作次数
    scanf("%d%d", &n, &m);

    // 步骤1：读入每个节点的初始权值
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]);

    // 步骤2：初始化并查集 —— 每个节点初始自成一个堆，父节点是自身
    for (int i = 1; i <= n; i++) fa[i] = i;

    // 步骤3：初始化空节点的dis为-1（左偏树的约定，保证dis计算正确）
    dis[0] = -1;

    // 步骤4：处理m个操作
    for (int op, x, y; m; m--)  // op：操作类型；x/y：操作参数
    {
        scanf("%d", &op);
        if (op == 1)
        {
            // 操作1：合并两个节点所在的堆
            scanf("%d%d", &x, &y);

            // 跳过条件：若任一节点已被删除（v=-1），无需合并
            if (v[x] == -1 || v[y] == -1) continue;

            // 找到x和y所在堆的根节点（并查集路径压缩）
            x = find(x), y = find(y);

            // 若两个堆不是同一个（根不同），则合并
            if (x != y)
            {
                // 合并两个堆，更新合并后根节点的父节点（相互指向新根）
                fa[x] = fa[y] = merge(x, y);
            }
        }
        else
        {
            // 操作2：删除指定节点所在堆的堆顶，并输出堆顶值
            scanf("%d", &x);

            // 若x已被删除，输出-1
            if (v[x] == -1)
            {
                printf("-1\n");
                continue;
            }

            // 找到x所在堆的根节点（堆顶）
            x = find(x);

            // 输出堆顶值（小根堆的堆顶是最小值）
            printf("%d\n", v[x]);

            // 标记堆顶节点为已删除（v=-1）
            v[x] = -1;

            // 步骤：将堆顶的左右子树合并，作为新的堆根
            // 并更新并查集：左右子树和原堆顶的父节点都指向新根
            fa[lc[x]] = fa[rc[x]] = fa[x] = merge(lc[x], rc[x]);
        }
    }
    return 0;
}

K-D树

视频讲解：https://www.bilibili.com/video/BV1sz4y1x7v1/

洛谷P1429 平面最近点对 https://www.luogu.com.cn/problem/P1429

#include <bits/stdc++.h>
// 宏定义：简化左/右子树的访问（lc = t[p].l，rc = t[p].r），减少代码冗余
#define lc t[p].l    // lc：节点p的左孩子索引
#define rc t[p].r    // rc：节点p的右孩子索引
using namespace std;

// ===================== 常量与全局变量定义 =====================
const int N = 200010;       // KD树最大节点数（适配题目数据范围）
double ans = 2e18;          // 全局变量：存储所有点对的最小距离，初始化为极大值
int n, K, root, cur;        // n：点的总数；K：当前构建/查询时的划分维度；root：KD树的根节点；cur：当前查询的点的索引

// ===================== KD树节点结构体 =====================
struct KD
{
    int l, r;               // 左、右孩子的索引（0表示无孩子）
    double v[2];            // 节点存储的二维坐标：v[0] = x坐标，v[1] = y坐标
    double L[2], U[2];      // 以当前节点为根的子树所覆盖的矩形区域范围：
                            // L[i] = 子树在第i维度的最小值，U[i] = 子树在第i维度的最大值
    // 重载小于运算符：用于nth_element按当前划分维度K排序
    // 作用：判断当前节点是否小于另一个节点b（按维度K的坐标比较）
    bool operator<(const KD &b) const { return v[K] < b.v[K]; }
} t[N];  // 存储所有KD树节点的数组

// ===================== 核心辅助函数 =====================
// 功能：更新节点p的子树矩形范围（L/U数组）
// 原理：子树的矩形范围 = 自身坐标 ∪ 左子树矩形范围 ∪ 右子树矩形范围
// 调用时机：构建子树后、修改子树结构后（保证范围的正确性）
void pushup(int p)
{
    // 遍历两个维度（x和y），分别更新范围
    for (int i = 0; i < 2; i++)
    {
        // 初始时，子树范围仅包含当前节点自身的坐标
        t[p].L[i] = t[p].U[i] = t[p].v[i];
        
        // 如果有左孩子，更新为「当前范围」和「左子树范围」的并集
        if (lc)
        {
            t[p].L[i] = min(t[p].L[i], t[lc].L[i]);  // 取最小值更新左边界
            t[p].U[i] = max(t[p].U[i], t[lc].U[i]);  // 取最大值更新右边界
        }
        
        // 如果有右孩子，更新为「当前范围」和「右子树范围」的并集
        if (rc)
        {
            t[p].L[i] = min(t[p].L[i], t[rc].L[i]);
            t[p].U[i] = max(t[p].U[i], t[rc].U[i]);
        }
    }
}

// 功能：递归构建KD树（分治法）
// 参数：l/r - 当前处理的节点区间；k - 当前划分维度（0=x轴，1=y轴，交替使用）
// 返回值：当前子树的根节点索引
int build(int l, int r, int k)
{
    // 递归终止条件：区间无效（无节点），返回0（空节点）
    if (l > r) return 0;
    
    // 1. 找区间中点，作为当前子树的根（中位数划分，保证树的平衡）
    int m = (l + r) >> 1;  // 等价于(l+r)/2，整数除法
    
    // 2. 设置当前划分维度，用于后续的nth_element排序
    K = k;
    
    // 3. nth_element：将区间[l,r]的节点按维度k排序，使得t[m]是中位数
    // 效果：t[m]左边的节点维度k坐标 ≤ t[m]，右边的 ≥ t[m]，无需完全排序，效率更高
    nth_element(t + l, t + m, t + r + 1);
    
    // 4. 递归构建左、右子树，划分维度交替（k^1：0↔1）
    t[m].l = build(l, m - 1, k ^ 1);  // 左子树：区间[l,m-1]，维度切换
    t[m].r = build(m + 1, r, k ^ 1);  // 右子树：区间[m+1,r]，维度切换
    
    // 5. 更新当前根节点m的子树矩形范围
    pushup(m);
    
    // 返回当前子树的根节点索引
    return m;
}

// 功能：计算数值的平方（辅助距离计算，避免重复代码）
double sq(double x)
{
    return x * x;
}

// 功能：计算「当前查询点cur」到「节点p」的欧几里得距离的平方
// 注：使用距离平方而非原始距离，避免开平方的浮点开销，不影响大小比较
double dis(int p)
{
    double s = 0;
    // 遍历两个维度，累加坐标差的平方（欧几里得距离平方公式）
    for (int i = 0; i < 2; i++)
        s += sq(t[cur].v[i] - t[p].v[i]);
    return s;
}

// 功能：计算「当前查询点cur」到「节点p的子树矩形区域」的最小可能距离的平方
// 核心作用：剪枝（若该最小距离≥当前已知的最小距离，无需访问该子树）
// 返回值：点到矩形的最小距离平方（若p为空，返回极大值）
double dis2(int p)
{
    // 空节点，返回极大值（表示无需考虑该子树）
    if (!p) return 2e18;
    
    double s = 0;
    // 遍历两个维度，计算点到矩形的最小距离平方
    for (int i = 0; i < 2; ++i)
    {
        // 点到矩形的最小距离计算逻辑：
        // 1. 若点的坐标 > 矩形右边界U[i]：距离为 点坐标 - U[i]
        // 2. 若点的坐标 < 矩形左边界L[i]：距离为 L[i] - 点坐标
        // 3. 否则：点在矩形内，距离为0
        // 用max(..., 0.0)处理上述三种情况，避免负数
        s += sq(max(t[cur].v[i] - t[p].U[i], 0.0)) +  // 右边界外的距离平方
             sq(max(t[p].L[i] - t[cur].v[i], 0.0));  // 左边界外的距离平方
    }
    return s;
}

// 功能：递归查询「当前查询点cur」的最近邻点，更新全局最小距离ans
// 参数：p - 当前访问的子树根节点
void query(int p)
{
    // 递归终止条件：空节点，直接返回
    if (!p) return;
    
    // 1. 更新全局最小距离：当前节点p不是查询点cur时，计算距离并更新ans
    if (p != cur)
        ans = min(ans, dis(p));
    
    // 2. 计算查询点到左、右子树矩形区域的最小距离（用于剪枝和访问顺序）
    double dl = dis2(lc);  // 到左子树的最小距离平方
    double dr = dis2(rc);  // 到右子树的最小距离平方
    
    // 3. 优先访问「可能更近」的子树（剪枝核心）：
    // 先访问距离更小的子树，若该子树的最小距离≥ans，无需访问另一子树
    if (dl < dr)
    {
        // 左子树更近：若左子树的最小距离 < 当前ans，才递归访问左子树
        if (dl < ans) query(lc);
        // 右子树：仅当最小距离 < 当前ans时，才递归访问（否则剪枝）
        if (dr < ans) query(rc);
    }
    else
    {
        // 右子树更近：优先访问右子树
        if (dr < ans) query(rc);
        // 左子树：剪枝判断
        if (dl < ans) query(lc);
    }
}

// ===================== 主函数（处理输入输出） =====================
int main()
{
    // 1. 读取点的总数
    scanf("%d", &n);
    
    // 2. 读取每个点的二维坐标（x,y）
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &t[i].v[0], &t[i].v[1]);
    
    // 3. 构建KD树：区间[1,n]，初始划分维度0（x轴）
    root = build(1, n, 0);
    
    // 4. 对每个点，查询其最近邻点，更新全局最小距离ans
    for (cur = 1; cur <= n; cur++)
        query(root);
    
    // 5. 输出最小距离（之前存储的是距离平方，需开平方），保留4位小数
    printf("%.4lf\n", sqrt(ans));
    
    return 0;
}

Splay树

视频讲解：https://www.bilibili.com/video/BV1wg411Z7Qa/

洛谷P3369 普通平衡树

#include <bits/stdc++.h>
using namespace std;

// ===================== 常量与全局变量定义 =====================
// N：节点最大数量（根据题目数据范围设定）；INF：哨兵值（避免边界判断）
const int N = 1100010, INF = (1 << 30) + 1;
// ch[x][0]：节点x的左孩子，ch[x][1]：节点x的右孩子
int ch[N][2];
// fa[x]：节点x的父节点
int fa[N];
// val[x]：节点x存储的数值（点权）
int val[N];
// cnt[x]：数值val[x]出现的次数（处理重复值）
int cnt[N];
// siz[x]：以x为根的子树的节点总数（包含重复值，即siz[x] = 左子树siz + 右子树siz + cnt[x]）
int siz[N];
// root：Splay树的根节点编号
int root;
// tot：节点总数计数器（用于分配新节点编号）
int tot;

// ===================== 核心辅助函数 =====================
// 功能：更新节点x的子树大小（旋转/插入/删除后必须调用，保证siz的正确性）
// 原理：子树大小 = 左子树大小 + 右子树大小 + 当前节点的数值计数
void pushup(int x)
{
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}

// 功能：旋转操作（Splay树的核心，用于调整树的结构，分为左旋/右旋）
// 作用：将节点x向上旋转一层，降低树的高度，保证Splay的均摊复杂度
// 参数：x - 要旋转的节点
void rotate(int x)
{
      /*
       gx                 gx
       |                  |
       fx                 x
       /\       ==>        / \
      x  o                o  fx
     /\                    /\
    o sx                   sx  o
    步骤 1：获取亲属节点与孩子类型
    步骤 2：重新连接树的三条核心边（保证结构不中断）
    步骤 3：自底向上更新节点状态
     */
  	
    // 1. 先获取x的父节点(fx)、祖父节点(gx)
    int fx = fa[x]; // fx = father(x)
    int gx = fa[fx]; // gx = father(fx) = grandfather(x)

    // 2. 判断x是fx的左孩子还是右孩子：kx=0表示左孩子，kx=1表示右孩子
    int kx = (ch[fx][1] == x);
    // 判断fx是gx的左孩子还是右孩子：kf=0表示左孩子，kf=1表示右孩子
    int kf = (ch[gx][1] == fx);

    // 3. 获取x的"反向孩子"（即x的左/右孩子，与kx相反）：旋转后需要接管该节点
    int sx = ch[x][kx ^ 1];

    // 4. 核心：重新连接树的边（共3条边需要调整）
    // 第一步：将gx的kf位置指向x，x的父节点改为gx（x取代fx的位置）
    ch[gx][kf] = x;
    fa[x] = gx;
    // 第二步：将x的反向孩子位置指向fx，fx的父节点改为x（fx成为x的子节点）
    ch[x][kx ^ 1] = fx;
    fa[fx] = x;
    // 第三步：将fx的kx位置指向sx，sx的父节点改为fx（fx接管x的原反向孩子）
    ch[fx][kx] = sx;
    fa[sx] = fx;

    // 5. 旋转后更新fx和x的子树大小（先更新下层的fx，再更新上层的x）
    pushup(fx);
    pushup(x);
}

// 功能：伸展操作（将节点x旋转到目标位置k的子节点，k=0表示旋转到根节点）
// 原理：通过多次旋转（zig/zig-zig/zig-zag）将x上移，保证Splay的均摊O(logn)复杂度
// 参数：x - 要伸展的节点；k - 目标父节点（x最终成为k的子节点）
void splay(int x, int k)
{
    /*
     *       z
     *      /
     *     y
     *    /
     *   x
     * 直线型，先转y，再转x
     *
     *       z
     *      /
     *     y
     *      \
     *       x
     *  折线型，先转x，再转x
     */
    // 循环条件：x的父节点不是k，说明还需要继续旋转
    while (fa[x] != k)
    {
        int y = fa[x]; // y是x的父节点
        int z = fa[y]; // z是y的父节点（x的祖父节点）

        // 判断旋转类型：
        // 1. 直线型（zig-zig）：z!=k 且 (y是z的左孩子) == (x是y的左孩子) → 先旋y，再旋x
        // 2. 折线型（zig-zag）：z!=k 且 (y是z的左孩子) != (x是y的左孩子) → 先旋x，再旋x
        if (z != k)
        {
            (ch[y][0] == x) ^ (ch[z][0] == y) ? rotate(x) : rotate(y);
        }
        // 最后旋转x，将x上移一层
        rotate(x);
    }
    // 如果k=0（目标是根节点），更新root为x
    if (k == 0) root = x;
}

// ===================== 功能函数（插入/删除/查询） =====================
// 功能：插入数值v到Splay树中
// 处理逻辑：
// 1. 若v已存在：仅增加cnt计数
// 2. 若v不存在：新建节点，插入到对应位置，最后将该节点splay到根
void insert(int v)
{
    int x = root; // 从根节点开始遍历
    int p = 0; // p记录x的父节点（遍历过程中更新）

    // 遍历树，找到v的插入位置（直到x为空，或找到值为v的节点）
    while (x != 0 && val[x] != v)
    {
        p = x; // 记录父节点
        // 决定走向左子树还是右子树：v>val[x]则走右子树（ch[x][1]），否则走左子树（ch[x][0]）
        x = ch[x][v > val[x]];
    }

    // 情况1：找到值为v的节点 → 仅增加计数
    if (x != 0)
    {
        cnt[x]++;
    }
    // 情况2：未找到v → 新建节点
    else
    {
        x = ++tot; // 分配新节点编号
        ch[p][v > val[p]] = x; // 将新节点挂到父节点p的对应位置
        fa[x] = p; // 设置新节点的父节点为p
        val[x] = v; // 设置新节点的数值为v
        cnt[x] = 1; // 初始计数为1
        siz[x] = 1; // 初始子树大小为1
    }

    // 将插入/更新后的节点x伸展到根，保证Splay的性质
    splay(x, 0);
}

// 功能：查找数值v对应的节点，并将该节点伸展到根（为后续前驱/后继/删除操作做准备）
// 原理：从根开始遍历，找到值为v的节点（或最接近v的节点），然后splay到根
void find(int v)
{
    int x = root;
    // 遍历条件：x的对应子树存在，且当前节点值不等于v
    while (ch[x][v > val[x]] != 0 && val[x] != v)
    {
        // 继续向目标子树遍历
        x = ch[x][v > val[x]];
    }
    // 将找到的节点伸展到根
    splay(x, 0);
}

// 功能：查找数值v的前驱（小于v的最大数）
// 返回值：前驱节点的编号（后续可通过val[]获取具体数值）
int getpre(int v)
{
    // 先找到v并伸展到根，方便后续查找
    find(v);
    int x = root;

    // 情况1：根节点的值已经小于v → 根节点就是前驱
    if (val[x] < v) return x;

    // 情况2：根节点的值大于等于v → 找左子树的最右节点（左子树的最大值）
    x = ch[x][0];
    while (ch[x][1] != 0) // 一直向右走，直到没有右孩子
    {
        x = ch[x][1];
    }

    // 将前驱节点伸展到根，方便后续操作
    splay(x, 0);
    return x;
}

// 功能：查找数值v的后继（大于v的最小数）
// 返回值：后继节点的编号（后续可通过val[]获取具体数值）
int getsuc(int v)
{
    // 先找到v并伸展到根，方便后续查找
    find(v);
    int x = root;

    // 情况1：根节点的值已经大于v → 根节点就是后继
    if (val[x] > v) return x;

    // 情况2：根节点的值小于等于v → 找右子树的最左节点（右子树的最小值）
    x = ch[x][1];
    while (ch[x][0] != 0) // 一直向左走，直到没有左孩子
    {
        x = ch[x][0];
    }

    // 将后继节点伸展到根，方便后续操作
    splay(x, 0);
    return x;
}

// 功能：删除数值v（支持重复值删除）
// 核心逻辑：利用前驱+后继将待删除节点孤立，再删除
void del(int v)
{
    // 1. 获取v的前驱和后继节点
    int pre = getpre(v);
    int suc = getsuc(v);

    // 2. 将前驱pre伸展到根，后继suc伸展到pre的右孩子
    // 此时：待删除节点一定是suc的左孩子（因为pre < v < suc）
    splay(pre, 0);
    splay(suc, pre);
    /*
     *    pre
     *     /\
     *    o  suc
     *       /\
     *      v  o
     */
    // 3. 获取待删除节点del（suc的左孩子）
    int del_node = ch[suc][0];

    // 4. 处理删除：
    // 情况1：del_node的计数>1 → 仅减少计数，无需删除节点
    if (cnt[del_node] > 1)
    {
        cnt[del_node]--;
        splay(del_node, 0); // 更新后伸展到根
    }
    // 情况2：del_node的计数=1 → 直接删除该节点（断开suc的左孩子）
    else
    {
        ch[suc][0] = 0; // 断开连接
        splay(suc, 0); // 更新树结构
    }
}

// 功能：查询数值v的排名（即有多少个数严格小于v）
// 实现技巧：先插入v（保证v存在），根节点的左子树大小即为排名，最后删除v恢复原树
int getrank(int v)
{
    insert(v); // 插入v，确保v在树中
    int res = siz[ch[root][0]]; // 左子树大小 = 严格小于v的数的个数
    del(v); // 删除v，恢复原树
    return res;
}

// 功能：查询排名为k的数值（第k小的数）
// 原理：根据子树大小遍历，左子树大小<k则走右子树，否则走左子树
int getval(int k)
{
    int x = root; // 从根节点开始遍历
    while (true)
    {
        // 情况1：k <= 左子树大小 → 目标在左子树
        if (k <= siz[ch[x][0]])
        {
            x = ch[x][0];
        }
        // 情况2：k <= 左子树大小 + 当前节点计数 → 目标就是当前节点
        else if (k <= siz[ch[x][0]] + cnt[x])
        {
            break;
        }
        // 情况3：k > 左子树大小 + 当前节点计数 → 目标在右子树，更新k
        else
        {
            k -= siz[ch[x][0]] + cnt[x];
            x = ch[x][1];
        }
    }
    splay(x, 0); // 将目标节点伸展到根，优化后续操作
    return val[x];
}

// ===================== 主函数（处理输入输出） =====================
int main()
{
    // 插入两个哨兵节点（-INF和INF），避免边界判断（如查询最小值的前驱、最大值的后继）
    insert(-INF);
    insert(INF);

    int n, op, x;
    scanf("%d", &n); // 读取操作次数
    while (n--)
    {
        scanf("%d%d", &op, &x); // 读取操作类型和参数
        switch (op)
        {
            case 1: insert(x); // 操作1：插入数值x
                break;
            case 2: del(x); // 操作2：删除数值x
                break;
            case 3: printf("%d\n", getrank(x)); // 操作3：查询x的排名
                break;
            // 操作4：查询第x小的数（+1是因为哨兵-INF占了第1位）
            case 4: printf("%d\n", getval(x + 1));
                break;
            case 5: printf("%d\n", val[getpre(x)]); // 操作5：查询x的前驱
                break;
            case 6: printf("%d\n", val[getsuc(x)]); // 操作6：查询x的后继
                break;
        }
    }
    return 0;
}

FHQ Treap

https://www.bilibili.com/video/BV1kY4y1j7LC/

P3369 普通平衡树

FHQ Treap 是无旋转版本的 Treap，是一种高效的平衡二叉搜索树（BST），核心通过「分裂（split）」和「合并（merge）」替代传统 Treap 的旋转操作，兼具实现简洁、逻辑清晰、功能完备的特点，可高效支持插入、删除、排名、第k大、前驱/后继等操作。

一、核心算法思想

FHQ Treap 的核心是双性质融合 + 无旋式结构调整：

1. BST 有序性：每个节点的键值满足「左子树所有节点 val < 根 val < 右子树所有节点 val」，保证有序性，是实现排名、第k大等查询的基础；

2. 随机堆平衡性：为每个节点分配随机值 rnd，满足「父节点 rnd < 子节点 rnd」（小根堆），通过随机性打散树的结构，避免普通 BST 退化成链表，保证均摊时间复杂度为 $O(\log n)$；

3. 无旋式调整：放弃传统 Treap 的旋转操作，仅通过「分裂」和「合并」两个原子操作实现所有功能，逻辑更简洁，避免旋转带来的边界错误。

二、核心关键点

1. 节点结构设计（功能支撑）

每个节点需同时维护 BST 和堆的核心属性，以及辅助查询的元信息：

字段	含义
l/r	左右子节点索引（0 表示空节点），支撑 BST 结构
val	节点键值，BST 排序依据（左子树 < 根 < 右子树）
rnd	随机值，堆排序依据（小根堆：父 rnd < 子 rnd），保证树平衡
size	以当前节点为根的子树大小，支撑「排名」「第k大」等查询（核心辅助字段）

2. 核心辅助函数（基础支撑）

（1）newnode：创建新节点

• 功能：为插入的键值分配唯一节点索引，初始化节点属性；

• 关键：rnd 用 rand() 生成随机值（保证堆的随机性），size 初始化为 1（仅包含自身）。

（2）pushup：更新子树大小

• 功能：子节点结构变化（分裂/合并/插入/删除）后，更新当前节点的 size；

• 公式：size = 左子树 size + 右子树 size + 1（1 为节点自身）；

• 关键：所有修改子树结构的操作后必须调用，保证 size 准确性（排名、第k大查询依赖 size）。

3. 核心原子操作：分裂（split）+ 合并（merge）

FHQ Treap 的所有功能（插入、删除、查询）均基于这两个操作实现，是算法的核心。

（1）分裂（split）：按键值拆分 BST

目标：将一棵 Treap 拆分为两棵树 x 和 y，满足「x 所有节点 val ≤ v，y 所有节点 val > v」；

实现逻辑（递归）：

• • 终止条件：当前节点为空，x=y=0；

  • 若当前节点 val ≤ v：归为 x 树，递归分裂其右子树，将右子树拆分为 x 的右子树和 y；

  • 若当前节点 val > v：归为 y 树，递归分裂其左子树，将左子树拆分为 x 和 y 的左子树；

  • 关键：分裂后调用 pushup 更新子树大小，保证 size 准确。

（2）合并（merge）：按堆性质合并 BST

• 前提：待合并的两棵树 x 和 y 满足「x 所有节点 val ≤ y 所有节点 val」（保证合并后仍是 BST）；

• 目标：合并为一棵 Treap，同时维持小根堆性质（父 rnd < 子 rnd）；

• 实现逻辑（递归）：

  • 终止条件：一棵为空则返回另一棵（x+y 简化空节点判断）；

  • 若 x的右子树和y（保证 BST 有序）；

  • 若 x.rnd < y.rnd ： x 作为根，递归合并 x 的右子树和 y （保证 BST 有序）；

  • 若 x.rnd > y.rnd：y 作为根，递归合并 x 和 y 的左子树（保证 BST 有序）；

  • 关键：合并后调用 pushup 更新子树大小，堆性质通过 rnd 比较保证，避免树失衡。

4. 功能操作实现（基于分裂+合并）

所有功能均通过「分裂→处理→合并」的流程实现，核心是利用分裂拆分出目标区间，处理后再合并恢复树结构。

操作	实现逻辑
插入（v）	1. 分裂原树为 x(val≤v) 和 y(val>v)；2. 创建新节点 z；3. 合并 x+z+y
删除（v）	1. 分裂原树为 x(val≤v) 和 z(val>v)；2. 分裂 x 为 x(val≤v-1) 和 y(val=v)；3. 合并 y 的左右子树（删除根）；4. 合并 x+处理后的y+z
查询排名（v）	1. 分裂原树为 x(val≤v-1) 和 y(val≥v)；2. 排名 = x.size + 1；3. 合并 x+y
查询第k大（k）	递归遍历： - 左子树 size+1 = k → 当前节点是答案； - k ≤ 左子树 size → 查左子树； - 否则查右子树（k -= 左子树 size+1）
查询前驱（v）	1. 分裂原树为 x(val≤v-1) 和 y(val≥v)；2. 前驱 = x 的第 x.size 大；3. 合并 x+y
查询后继（v）	1. 分裂原树为 x(val≤v) 和 y(val>v)；2. 后继 = y 的第 1 大；3. 合并 x+y

5. 关键设计细节（避坑&效率）

1. 随机值的作用：rnd 随机生成，通过堆性质强制树的平衡，避免最坏情况（如有序插入导致的链表）；

2. 空节点处理：空节点索引为 0，size=0，分裂/合并时通过 !p 判断空节点，简化边界；

3. 查询后恢复树结构：排名、前驱/后继等查询操作仅需临时分裂，处理后必须合并，保证原树结构不变；

4. 删除逻辑优化：通过两次分裂精准拆分出「仅包含 v 的子树 y」，合并 y 的左右子树即可删除一个 v（支持重复值删除）；

5. 时间复杂度保障：分裂和合并均为递归遍历树的高度，堆性质保证树高为 $O(\log n)$，因此所有操作均摊 $O(\log n)$。

三、核心优势

1. 逻辑简洁：无旋转操作，仅依赖分裂+合并，代码量少、边界条件少，易于实现和调试；

2. 功能完备：支持所有 BST 核心操作，且可扩展区间操作（如区间翻转、区间求和）；

3. 稳定性高：随机堆性质避免退化，均摊效率稳定，适合处理 1e5 级别的数据量。

四、传址调用

1. 先搞懂：传址调用（引用传递）到底是什么？

简单说：引用就是变量的“别名”，函数里操作这个“别名”，就等同于直接操作函数外的原变量； 对比“传值调用”（函数会复制一份变量，改的是拷贝，原变量不变），传址调用能让函数里的修改，直接反映到函数外的变量上。

举个生活例子：

• 传值调用：你复制了一把家里的钥匙给朋友，朋友改了钥匙的形状，你手里的原钥匙完全没变化；

• 传址调用：你把家里的原钥匙给朋友，朋友改了钥匙形状，你手里的钥匙也跟着变了。

2.代码中传址调用的具体场景 & 为什么必须用？

场景1：newnode 函数中的 int &x

void newnode(int &x, int v) 
{
    x = ++idx;  // 给x赋值新节点的索引
    // ... 其他初始化
}

• 作用：创建新节点后，把新节点的索引（idx++）赋值给函数外的原变量；

• 为什么必须用引用： 如果不用引用（改成 int x），函数里的 x 只是原变量的“拷贝”，函数执行完，外部变量还是原来的值，根本拿不到新节点的索引，插入操作就会失败。

• 举例：插入时调用 newnode(z, v)，z 是外部变量，函数里 x=++idx 其实就是给 z 赋值，拿到新节点的索引。

场景2：split 函数中的 int &x, int &y

void split(int p, int v, int &x, int &y) {
    if (!p) {
        x = y = 0;  // 给x、y赋值为空节点
        return;
    }
    if (tr[p].val <= v) {
        x = p;  // 把当前节点归为x树，赋值给外部的x
        split(tr[x].r, v, tr[x].r, y);
        // ...
    } else {
        y = p;  // 把当前节点归为y树，赋值给外部的y
        split(tr[y].l, v, x, tr[y].l);
        // ...
    }
}

• 作用：split 的核心是把一棵树拆成 x（val≤v）和 y（val>v）两棵树，需要把拆分后的两棵树的根节点索引，赋值给函数外的 x 和 y；

• 为什么必须用引用： 如果 x、y 是传值调用，函数里给 x=0、x=p 这些赋值，只会改拷贝，外部的 x、y 还是初始值（比如0），根本拿不到拆分后的结果，后续的合并、插入、删除操作都没法做。

• 举例：插入操作中调用 split(root, v, x, y)，外部定义的 x、y 原本是随机值，经过 split 后，x 变成“val≤v的树的根”，y 变成“val>v的树的根”——这全靠引用才能把结果“带出来”。

3. 总结：FHQ Treap 中传址调用的核心目的

所有传址调用（引用）都服务于一个需求：让函数把内部计算的结果（新节点索引、分裂后的根节点）“回传”到函数外部。 因为 FHQ Treap 的核心是“分裂+合并”，这两个操作需要把处理后的树的根节点索引传递出去，而传值调用做不到这一点，只能用引用（传址）。

4. 一句话通俗总结

代码里的传址调用（引用），就是为了让函数能“直接修改”外面的变量，把分裂、创建节点的结果传递出来，否则 Treap 的核心操作（分裂、合并、插入）都没法完成。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 节点数组最大容量（适配 1e5 级数据量）
const int N = 100005;

// Treap 节点结构体：每个节点同时维护 BST 和堆的性质
struct node
{
    int l, r; // 左右儿子的节点索引（0 表示空节点）
    int val; // BST 键值（排序依据，满足左子树 < 根 < 右子树）
    int rnd; // 随机值（堆的排序依据，维持树的平衡，避免退化成链）
    int size; // 以当前节点为根的子树大小（用于快速计算排名、第k大）
} tr[N];

int root; // Treap 的根节点索引（初始为 0，即空树）
int idx; // 节点计数器（用于分配新节点的唯一索引，从 1 开始）

// 创建新节点：x 是引用（用于修改外部变量，存储新节点索引），v 是节点的键值
void newnode(int &x, int v)
{
    x = ++idx; // 分配新节点索引（idx 自增，保证唯一）
    tr[x].val = v; // 初始化节点键值
    tr[x].rnd = rand(); // 生成随机值（维持堆性质）
    tr[x].size = 1; // 新节点初始子树大小为 1（仅自身）
}

// 上传子树大小信息：当子节点变化时，更新当前节点的 size（核心辅助函数）
// p 为当前节点索引，size = 左子树大小 + 右子树大小 + 1（自身）
void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

// 分裂操作（Treap 核心操作）：将以 p 为根的 BST 按键值分裂为两棵树
// 分裂规则：x 树所有节点 val <= v，y 树所有节点 val > v
// p：当前待分裂的子树根；v：分裂基准值；x/y：分裂后两棵树的根（引用传递）
void split(int p, int v, int &x, int &y)
{
    if (!p)
    {
        // 递归终止：当前节点为空，x 和 y 均为空
        x = y = 0;
        return;
    }
    if (tr[p].val <= v)
    {
        // 当前节点 val <= v，归为 x 树
        x = p; // x 树的根设为当前节点
        // 递归分裂当前节点的右子树，将右子树分裂为 x 的右子树和 y
        split(tr[x].r, v, tr[x].r, y);
        pushup(x); // 分裂后更新 x 树的大小
    }
    else // 当前节点 val > v，归为 y 树
    {
        y = p; // y 树的根设为当前节点
        // 递归分裂当前节点的左子树，将左子树分裂为 x 和 y 的左子树
        split(tr[y].l, v, x, tr[y].l);
        pushup(y); // 分裂后更新 y 树的大小
    }
}

// 合并操作（Treap 核心操作）：将两棵 BST 合并为一棵 Treap
// 合并前提：x 树所有节点 val <= y 树所有节点 val（保证合并后仍是 BST）
// 合并规则：按 rnd 维持小根堆性质（rnd 小的作为父节点，保证树平衡）
int merge(int x, int y)
{
    if (!x || !y) return x + y; // 递归终止：一棵为空则返回另一棵（0+非0=非0，0+0=0）
    if (tr[x].rnd < tr[y].rnd)
    {
        // x 的 rnd 更小，x 作为合并后的根
        tr[x].r = merge(tr[x].r, y); // 递归合并 x 的右子树和 y
        pushup(x); // 合并后更新 x 的大小
        return x;
    } else
    {
        // y 的 rnd 更小，y 作为合并后的根
        tr[y].l = merge(x, tr[y].l); // 递归合并 x 和 y 的左子树
        pushup(y); // 合并后更新 y 的大小
        return y;
    }
}

// 插入操作：向 Treap 中插入键值 v
void insert(int v)
{
    int x, y, z;
    // 1. 先将原树分裂为 x（val <= v）和 y（val > v）
    split(root, v, x, y);
    // 2. 创建新节点 z（存储 v）
    newnode(z, v);
    // 3. 先合并 x 和 z（保证 x 中元素 <= z），再合并结果和 y（保证整体 BST 性质）
    root = merge(merge(x, z), y);
}

// 删除操作：从 Treap 中删除一个键值为 v 的节点（若有多个，仅删除一个）
void del(int v)
{
    int x, y, z;
    // 1. 第一次分裂：将原树分为 x（val <= v）和 z（val > v）
    split(root, v, x, z);
    // 2. 第二次分裂：将 x 分为 x（val <= v-1）和 y（val = v）
    split(x, v - 1, x, y);
    // 3. 删除 y 的根节点：合并 y 的左右子树（跳过根节点，即删除一个 v）
    y = merge(tr[y].l, tr[y].r);
    // 4. 合并 x、处理后的 y、z，恢复原树结构
    root = merge(merge(x, y), z);
}

// 查询操作：查询键值 v 的排名（排名 = 比 v 小的数的个数 + 1）
int getrank(int v)
{
    int x, y;
    // 1. 分裂原树为 x（val <= v-1）和 y（val >= v）
    split(root, v - 1, x, y);
    // 2. x 的大小就是比 v 小的数的个数，排名 = x.size + 1
    int ans = tr[x].size + 1;
    // 3. 合并 x 和 y，恢复原树（查询不修改树结构）
    root = merge(x, y);
    return ans;
}

// 查询操作：查询第 k 名的键值（k 从 1 开始，1 是最小数）
int getval(int root, int k)
{
    // 左子树大小 + 1 == k：当前节点就是第 k 名
    if (k == tr[tr[root].l].size + 1)
        return tr[root].val;
        // k <= 左子树大小：第 k 名在左子树中，递归查询左子树
    else if (k <= tr[tr[root].l].size)
        return getval(tr[root].l, k);
        // 否则：第 k 名在右子树中，递归查询右子树（k 需减去左子树大小 + 1）
    else
        return getval(tr[root].r, k - tr[tr[root].l].size - 1);
}

// 查询操作：查询 v 的前驱（比 v 小的最大数）
int getpre(int v)
{
    int x, y, s, ans;
    // 1. 分裂原树为 x（val <= v-1）和 y（val >= v）
    split(root, v - 1, x, y);
    s = tr[x].size; // x 的大小是比 v 小的数的个数
    ans = getval(x, s); // x 中第 s 名（最大数）就是前驱
    root = merge(x, y); // 恢复原树
    return ans;
}

// 查询操作：查询 v 的后继（比 v 大的最小数）
int getnxt(int v)
{
    int x, y, ans;
    // 1. 分裂原树为 x（val <= v）和 y（val > v）
    split(root, v, x, y);
    ans = getval(y, 1); // y 中第 1 名（最小数）就是后继
    root = merge(x, y); // 恢复原树
    return ans;
}

// 主函数：处理输入输出，执行对应操作
int main()
{
    int n, op, v;
    scanf("%d", &n); // 读取操作总数 n
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &op, &v); // 读取操作类型 op 和参数 v
        if (op == 1) insert(v); // op=1：插入 v
        else if (op == 2) del(v); // op=2：删除 v
        else if (op == 3) printf("%d\n", getrank(v)); // op=3：查询 v 的排名
        else if (op == 4) printf("%d\n", getval(root, v)); // op=4：查询第 v 名的数
        else if (op == 5) printf("%d\n", getpre(v)); // op=5：查询 v 的前驱
        else printf("%d\n", getnxt(v)); // op=6：查询 v 的后继
    }
    return 0;
}

主席树

https://www.bilibili.com/video/BV1PT411L7XQ/

P3834 可持久化线段树2

主席树（也称可持久化线段树）是针对静态数组区间第k小查询的经典数据结构，核心是「可持久化」与「权值线段树」的结合，通过保留线段树的历史版本、压缩大值域、动态开点等设计，高效解决“值域大但元素数量有限”的区间排名查询问题。

一、核心算法思想

1. 核心目标

解决静态数组（数组构建后不修改）的多次「区间第k小」查询，适配以下场景：

• 数组元素值域极大（如 1e9），无法直接构建对应长度的线段树；

• 数组元素数量有限（如 n≤2e5），需保证查询效率（单次 O(logn)）。

2. 核心原理

（1）权值线段树基础

权值线段树的核心是「统计值域区间内的元素出现次数」，而非传统线段树的「区间求和/最值」：

• 每个节点对应一个「值域区间」（如 [l, r]）；

• sum[u] 记录该值域区间内的元素出现次数；

• 查找第k小的逻辑：若左子树的计数 ≥k，说明第k小在左子树；否则在右子树（k 减去左子树计数）。

（2）可持久化（版本保留）

普通线段树修改会覆盖原有结构，而主席树通过「差异复制」保留所有历史版本：

• 每个版本对应「前i个元素构建的权值线段树」（root[i] 是第i版的根节点）；

• 新增元素时，不修改旧版本节点，仅新建「路径上的差异节点」，其余节点与旧版本共享（节省空间）；

• 区间 [l, r] 的权值分布 = 第r版线段树 - 第l-1版线段树（前缀和思想）。

（3）离散化：压缩大值域

由于元素值域可能极大（如 1e9），直接构建线段树会超出空间，因此将原始值映射到「连续的小范围下标」（如 [1, bn]，bn≤n）：

• 步骤：复制数组 → 排序 → 去重 → 用 lower_bound 映射原始值到离散化下标。

（4）动态开点：节省空间

不预先构建满二叉树（静态线段树需 4*n 空间，值域大时不可行），仅在插入元素时创建需要的节点，通过 tot 计数器分配唯一节点编号，空间复杂度优化为 O(nlogn)。

二、核心关键点

1. 离散化（值域压缩的核心）

操作步骤	代码对应逻辑	作用
复制数组	b[i] = a[i]	保留原始数组，用辅助数组b做离散化
排序	sort(b+1, b+n+1)	让相同元素相邻，为去重做准备
去重	unique(...) - b -1	得到离散化后的值域长度bn
映射	lower_bound(...) - b	将原始值a[i]映射到离散化下标p（∈[1, bn]）

2. 可持久化的核心设计

（1）版本管理

• root[i]：第i个版本线段树的根节点，root[0] 代表空树（无元素）；

• 构建过程：从 root[0] 开始，依次插入每个元素，生成 root[1] ~ root[n]，每个版本仅比前一版本多一条更新路径的节点。

（2）差异复制（change函数）

u = ++tot;          // 新建节点（不修改旧节点v）
ls[u] = ls[v];      // 继承旧版本左儿子（共享结构）
rs[u] = rs[v];      // 继承旧版本右儿子（共享结构）
sum[u] = sum[v] + 1;// 仅更新计数（新增一个元素）

• 核心：仅更新插入元素路径上的节点，其余节点与旧版本完全共享，空间效率为 O(nlogn)。

（3）动态开点

• tot 作为节点计数器，初始为0，每次创建节点时 tot++，保证节点编号唯一；

• ls[N*20]/rs[N*20]：预留 n*20 个节点（经验值，适配 n=2e5 时 log2(n)≈18），避免空间溢出。

3. 区间第k小查询的核心逻辑（query函数）

int s = sum[ls[u]] - sum[ls[v]];  // 区间[l..r]在左子树值域的元素个数
if (k <= s) 
    return query(ls[u], ls[v], l, mid, k);  // 第k小在左子树
else 
    return query(rs[u], rs[v], mid+1, r, k-s);  // 第k小在右子树

• u=root[r]，v=root[l-1]：通过前缀和差，得到区间 [l, r] 的权值分布；

• s 是区间 [l, r] 落在左子树值域的元素个数，通过比较 s 和 k 递归定位第k小元素。

4. 关键操作流程

阶段	操作	目的
预处理	离散化 → 构建n个版本的主席树	将原始数组转化为可查询的版本化权值线段树
查询	计算root[r]-root[l-1] → 递归找第k小的离散化下标 → 映射回原始值	得到区间[l,r]的第k小元素

5. 时间/空间复杂度 & 适用场景

维度	复杂度	说明
预处理	O(nlogn)	每个元素插入需递归 logn 层，创建 logn 个节点
单次查询	O(logn)	递归深度为离散化后的值域长度的对数（logbn ≈ logn）
空间	O(nlogn)	每个元素插入新增 logn 个节点，总节点数约 nlogn
适用场景	静态数组、值域大（1e9）、数量有限（n≤2e5）、多次区间第k小查询	不支持数组修改（静态），若需动态修改需用树状数组套主席树

三、核心优势

1. 高效查询：单次区间第k小查询仅 O(logn)，适配多次查询场景；

2. 空间优化：版本间共享大部分节点，仅存储差异，空间复杂度 O(nlogn)；

3. 值域适配：离散化+动态开点解决大值域问题，无需依赖元素值域范围；

4. 实现简洁：核心仅「构建（change）+ 查询（query）」两个函数，逻辑清晰。

四、核心避坑点

1. 离散化细节：unique 需配合 sort 使用，且映射时需用 lower_bound（而非 upper_bound），避免下标错误；

2. 版本索引：root[i] 对应前i个元素，查询区间 [l,r] 需用 root[r] - root[l-1]，切勿写成 root[r] - root[l]；

3. 动态开点空间：节点数组需预留足够长度（如 N*20），否则会出现数组越界；

4. 递归终止条件：查询时当 l==r 时返回l（离散化下标），需映射回原始值 b[p] 再输出。

五、双指针同步搜索建树

1、先搞懂：“双指针同步搜索建树”的核心定义

在主席树的 change 函数（可持久化点更新）中，“双指针”指的是新版本节点指针 u 和 旧版本节点指针 v，“同步搜索”指的是这两个指针始终遍历线段树的同一层、对应同一个值域区间，同步定位到需要更新的节点路径——本质是让新版本线段树“复刻”旧版本的大部分结构，仅在插入元素的路径上创建新节点，是主席树“可持久化+空间优化”的核心。

2、为什么需要“双指针同步搜索”？

主席树的每个版本（root[i]）都是一棵权值线段树，且所有版本的线段树：

• 值域区间划分完全一致（都是离散化后的 [1, bn]）；

• 仅在“插入当前元素的路径”上有计数差异，其余结构完全相同。

如果不做“同步搜索”，新版本需要重新构建整棵树，空间复杂度会飙升到 O(n²)；而通过双指针同步遍历，新版本只需复制旧版本的非更新路径，仅在更新路径上创建新节点，空间复杂度能控制在 O(nlogn)。

3、结合代码拆解“双指针同步搜索”的完整过程

以 change 函数为例，我们逐行解释同步逻辑：

// u：新版本节点指针（引用传递，新建节点）；v：旧版本节点指针（继承结构）
// l, r：当前同步遍历的「值域区间」；p：待插入元素的离散化下标
void change(int &u, int v, int l, int r, int p)//先复制，后递归更新儿子
{
    // 步骤1：新建新版本节点（双指针起点：u和v同步指向当前值域区间的根）
    u = ++tot;           // 新版本创建新节点（u是新指针）
    ls[u] = ls[v];       // 复刻旧版本左儿子（非更新路径，直接共享）
    rs[u] = rs[v];       // 复刻旧版本右儿子（非更新路径，直接共享）
    sum[u] = sum[v] + 1; // 仅更新计数（当前值域区间元素数+1）

    if (l == r) return;  // 同步到叶子节点，终止搜索

    // 步骤2：双指针同步定位更新路径（核心！）
    if (p <= mid) {      // 插入位置在左子树值域 [l, mid]
        // 左指针同步：u的左儿子 和 v的左儿子 同步遍历左子树
        change(ls[u], ls[v], l, mid, p);
    } else {             // 插入位置在右子树值域 [mid+1, r]
        // 右指针同步：u的右儿子 和 v的右儿子 同步遍历右子树
        change(rs[u], rs[v], mid + 1, r, p);
    }
}

关键细节拆解：

（1）. 双指针的“同步性”体现在哪里？

• 值域同步：u 和 v 始终处理同一个值域区间 [l, r]（比如初始都是 [1, bn]，递归后都是 [l, mid] 或 [mid+1, r]）；

• 路径同步：u 和 v 走的是线段树的同一分支（左/右）——因为插入的 p 是固定的，所以两个指针会同步定位到 p 所在的叶子节点；

• 结构同步：非更新路径上，u 直接继承 v 的左/右儿子（ls[u]=ls[v]/rs[u]=rs[v]），保证所有版本的线段树结构完全一致。

（2）. “搜索”的目标是什么？

搜索的目标是找到待插入元素 p 对应的叶子节点（离散化后的值域单点）：

• 从根节点（root[i-1] 是旧版本根 v，root[i] 是新版本根 u）开始，同步向下遍历；

• 每一层都根据 p 落在左/右值域区间，决定双指针走左/右分支；

• 直到 l==r（叶子节点），就是 p 对应的位置，停止搜索。

（3）. 同步搜索的最终效果

假设我们要基于 root[2]（旧版本，前2个元素）创建 root[3]（新版本，插入第3个元素 p=5）：

• 双指针 u（root[3]）和 v（root[2]）同步从根出发，遍历到 p=5 所在的路径；

• 路径外的节点：u 直接复用 v 的子节点（共享结构，不占新空间）；

• 路径上的节点：u 新建节点，更新 sum 计数（仅这部分是新创建的，空间开销小）。

4、通俗类比：理解“双指针同步搜索”

把每个版本的线段树想象成一栋“值域大楼”，每层对应一个值域区间，每个房间是一个节点：

• 旧版本 v 是已经建好的大楼；

• 新版本 u 要在旧大楼基础上“加一个元素”，不需要重建整栋楼；

• 你（u 指针）和朋友（v 指针）同步从楼顶（根节点）出发，找要加元素的房间（叶子节点）；

• 大部分房间（非更新路径）你直接用朋友的钥匙（继承 ls/rs）；

• 只有到了要更新的房间路径上，你才新建一个房间（u=++tot），改一下房间里的计数（sum[u]=sum[v]+1）；

• 全程你们走的是同一层、同一条走廊（同步搜索），保证你新建的大楼和旧大楼结构完全一致。

5、避坑点：同步搜索的关键注意事项

1. 值域区间必须一致：递归时 l/r 必须同时传给 u 和 v 的子节点，不能修改，否则双指针会“走岔路”，导致版本结构不一致；

2. 引用传递 u：u 必须是引用（int &u），否则新建的节点编号无法“回传”到上层，新版本的结构会断裂；

3. 先复刻再递归：必须先执行 ls[u]=ls[v]/rs[u]=rs[v]，再递归更新子节点——先继承旧结构，再修改差异，顺序不能反。

参考代码

// 算法类型：可持久化权值线段树（主席树）+ 离散化 + 动态开点
// 核心功能：解决静态数组的区间第k小查询问题
// 时间复杂度：预处理 O(nlogn)，单次查询 O(logn)，整体 O(nlogn + mlogn)
// 适用场景：数组元素值域大（如 1e9）但数量有限（n≤2e5），需多次查询任意区间第k小
#include <bits/stdc++.h>  
using namespace std;     

#define N 200005    // 定义最大数据规模：原始数组长度n、查询次数m均≤2e5
#define mid ((l+r)>>1) // 线段树区间中点计算公式：等价于 (l+r)/2，位运算更高效（避免除法溢出）

// 全局变量定义
int n, m;   // n：原始数组的长度；m：查询请求的次数
int a[N];   // 存储原始输入数组（1-based下标，便于前缀和逻辑）
int b[N];   // 离散化辅助数组：复制a的所有元素，用于排序去重压缩值域

int root[N]; // root[i]：第i个版本线段树的根节点索引（可持久化核心：每个版本对应前i个元素的状态）
int tot;   // 动态开点的节点计数器：记录已创建的线段树节点总数（初始为0，随节点创建自增）

// 线段树节点的动态存储（不预先建满树，仅在需要时创建节点）
int ls[N * 20];   // ls[u]：节点u的左儿子索引（20是经验系数，适配n=2e5时log2(n)≈18，预留足够节点）
int rs[N * 20];   // rs[u]：节点u的右儿子索引
int sum[N * 20];  // sum[u]：节点u对应「值域区间」内的元素出现次数之和（权值线段树的核心存储）

// 构建空的权值线段树（仅初始化根节点，可选调用）
// 参数说明：
// u：当前节点索引（引用传递，用于存储新建节点的唯一编号）
// l, r：当前节点对应的「离散化后的值域区间」[l, r]
void build(int &u, int l, int r)
{
    u = ++tot;   // 动态开点：为当前空树分配根节点编号（tot自增保证节点编号唯一）
    if (l == r) return;  // 递归终止条件：到达叶子节点（对应单个离散化后的值，无左右儿子）
    build(ls[u], l, mid);  // 递归构建左子树：值域区间 [l, mid]
    build(rs[u], mid + 1, r);  // 递归构建右子树：值域区间 [mid+1, r]
}

// 可持久化点更新：基于旧版本线段树创建新版本，新增一个元素（核心操作）
// 参数说明：
// u：新版本线段树的节点索引（引用传递，存储新建节点编号）
// v：旧版本线段树的节点索引（继承其大部分结构，仅修改差异部分）
// l, r：当前节点对应的「离散化后的值域区间」[l, r]
// p：待插入元素的「离散化后下标」（即元素在b数组中的位置）
void change(int &u, int v, int l, int r, int p)
{
    u = ++tot;           // 动态开点：新建节点（可持久化核心：不修改旧节点v，仅创建差异节点）
    ls[u] = ls[v];       // 继承旧版本的左儿子（大部分节点结构共享，节省空间）
    rs[u] = rs[v];       // 继承旧版本的右儿子
    sum[u] = sum[v] + 1; // 更新当前节点的计数：新增一个元素p，对应值域区间的出现次数+1
    if (l == r) return;  // 递归终止条件：到达p对应的叶子节点，更新完成
    // 双指针同步搜索：根据p的位置决定更新左/右子树（保证线段树结构一致性）
    if (p <= mid)        // p落在左子树值域 [l, mid]，递归更新左子树
        change(ls[u], ls[v], l, mid, p);
    else                 // p落在右子树值域 [mid+1, r]，递归更新右子树
        change(rs[u], rs[v], mid + 1, r, p);
}

// 区间第k小查询：计算 [l..r] 区间内的第k小元素（返回离散化后的下标）
// 参数说明：
// u：第r版线段树的根（对应前r个元素的权值分布）
// v：第l-1版线段树的根（对应前l-1个元素的权值分布）
// l, r：当前查询的「离散化后的值域区间」[l, r]
// k：目标排名（1-based，即1对应区间最小元素）
int query(int u, int v, int l, int r, int k)
{
    if (l == r) return l;  // 递归终止条件：值域区间仅一个值，即为第k小元素（返回离散化下标）
    // 核心逻辑：利用前缀和差计算 [l..r] 区间落在左子树值域的元素个数
   	 // s = 前r个元素左子树计数 - 前l-1个元素左子树计数 = 区间[l..r]左子树元素个数
    int s = sum[ls[u]] - sum[ls[v]];
    if (k <= s)  // 左子树元素个数 ≥ k：第k小元素在左子树，递归查询左子树
        return query(ls[u], ls[v], l, mid, k);
    else         // 左子树元素个数 < k：第k小元素在右子树，递归查询右子树（k需减去左子树元素个数）
        return query(rs[u], rs[v], mid + 1, r, k - s);
}

int main()
{
    scanf("%d%d", &n, &m);  // 读取原始数组长度n和查询次数m（高效输入，适配大数据量）
    // 读取原始数组a，并复制到b数组（b用于离散化，不修改原始数组a）
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];  // a[i]存储原始值，b[i]同步复制

    // 步骤1：离散化（压缩值域，解决原始元素值域过大的问题）
    sort(b + 1, b + n + 1);  // 对b数组排序（排序是离散化的前提，确保相同元素相邻）
    // 去重：unique函数将重复元素移到数组尾部，返回去重后数组的尾指针
    // bn = 去重后数组的长度（1-based下标，离散化后的值域为 [1, bn]）
    int bn = unique(b + 1, b + n + 1) - b - 1;

     // 步骤2：构建可持久化权值线段树（每个版本对应前i个元素）
     // build(root[0], 1, bn);  
  	  // 可选：显式初始化空树（root[0]初始为0，代表空树，注释后不影响功能）
    for (int i = 1; i <= n; i++)
    {
        // 找到a[i]在离散化数组b中的下标p：lower_bound返回第一个≥a[i]的元素地址，减去b的起始地址得到下标
        int p = lower_bound(b + 1, b + bn + 1, a[i]) - b;
        // 基于前i-1版线段树（root[i-1]），创建第i版线段树（插入a[i]的离散化下标p）
        change(root[i], root[i - 1], 1, bn, p);
    }

    // 步骤3：处理m次区间第k小查询
    while (m--) // 循环m次，每次处理一个查询（m--等价于处理完一次查询后m减1）
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);  // 读取查询参数：区间[l..r]，目标排名k
        // 查询逻辑：root[r] - root[l-1] 得到区间[l..r]的权值分布，返回第k小的离散化下标p
        int p = query(root[r], root[l - 1], 1, bn, k);
        printf("%d\n", b[p]);  // 将离散化下标p映射回原始值（b[p]即区间第k小元素），输出结果
    }

    return 0;  // 程序正常结束
}

树套树（线段树套Splay）

https://www.bilibili.com/video/BV1Q14y147XF/

P3380 二逼平衡树（线段树+平衡树）

树套树是多层树形结构嵌套的复合数据结构，核心是“外层区间管理结构 + 内层有序维护结构”的分层协作，本文以「线段树套Splay」为例，拆解其解决“动态数组区间有序查询”的核心逻辑与关键设计。

一、核心算法思想

树套树的本质是分治+有序维护的分层协作：

1. 分层职责拆分：

   • 外层：用「线段树」做区间分治，将原数组划分为多个重叠的子区间，快速定位“覆盖目标区间的所有子区间”，解决“区间查询/更新”的范围问题；

   • 内层：用「Splay树」做有序维护，每个线段树节点绑定一棵Splay，存储该节点管辖子区间的所有元素并保持有序，解决“排名、第k小、前驱/后继”的有序查询问题。

2. 操作拆解逻辑： 把“动态数组的区间有序操作”拆解为：外层线段树定位目标子区间 → 内层Splay对每个子区间做有序统计/修改 → 合并子区间结果得到最终答案。

3. 效率保障： 外层线段树的区间定位是 $O(\log n)$，内层Splay的有序操作是 $O(\log n)$，嵌套后整体操作效率为 $O(\log^2 n)$，兼顾动态修改与有序查询的需求。

二、核心关键点

1. 嵌套结构设计（核心框架）

层级	数据结构	核心作用	关键细节
外层（区间层）	线段树	1. 对原数组做区间分治，每个节点管辖一个连续子区间； 2. 快速定位覆盖目标区间/更新位置的所有子区间；3. 聚合内层Splay的查询结果。	1. 标准线段树分治（mid=(l+r)>>1），lc=u<<1、rc=u<<1	1简化儿子访问；2. 每个线段树节点绑定一棵Splay（root[u]存储Splay根）；3. 元素会出现在O(logn)个线段树节点的Splay中（线段树区间覆盖特性）。
内层（有序层）	Splay树	1. 维护对应线段树节点管辖区间的所有元素（BST有序）；2. 高效支持插入、删除、排名、前驱/后继查询。	1. 用siz字段记录子树大小（排名/第k小的核心）；2. 旋转+Splay操作维持平衡，避免退化成链表；3. 插入-INF/INF哨兵，简化边界判断。

2. 核心操作的拆解与实现（执行流程）

（1）构建操作（预处理）

• 逻辑：外层线段树递归构建，每个线段树节点初始化时，向内层Splay插入该节点管辖区间的所有元素（含哨兵）；

• 本质：把原数组元素分散到外层线段树的各个节点的Splay中，为后续区间查询做准备；

• 复杂度：$O(n \log^2 n)$（线段树O(n)个节点，每个节点的Splay插入O(logn)）。

（2）单点更新操作（动态修改）

• 步骤： ① 外层：从线段树根节点递归找到所有包含更新位置pos的线段树节点（O(logn)个）； ② 内层：对每个找到的线段树节点的Splay，删除旧值、插入新值（Splay的del/insert操作）； ③ 同步更新原始数组w[pos]；

• 本质：更新所有包含pos的子区间的有序统计信息；

• 复杂度：$O(\log^2 n)$（外层O(logn)个节点，每个节点的Splay操作O(logn)）。

（3）区间有序查询（排名/前驱/后继）

• 排名查询（区间[x,y]中v的排名）： ① 外层：找到所有覆盖[x,y]的线段树节点（O(logn)个）； ② 内层：对每个节点的Splay查询“比v小的元素数”（减哨兵-INF的贡献）； ③ 合并：累加所有子区间的结果，排名=累加值+1；

• 前驱查询（区间[x,y]中v的前驱）： ① 外层：找到所有覆盖[x,y]的线段树节点； ② 内层：对每个节点的Splay查询前驱； ③ 合并：取所有子区间前驱的最大值；

• 后继查询（区间[x,y]中v的后继）： ① 外层：找到所有覆盖[x,y]的线段树节点； ② 内层：对每个节点的Splay查询后继； ③ 合并：取所有子区间后继的最小值；

• 复杂度：$O(\log^2 n)$（外层O(logn)个节点，每个节点的Splay操作O(logn)）。

（4）区间第k小查询（特殊拆解）

• 逻辑：无法直接拆解为子区间查询，需结合「二分答案+区间排名」；

• 步骤： ① 二分答案mid（值域范围如0~1e8）； ② 查询区间[x,y]中比mid小的元素数s； ③ 若s+1 ≤k，说明第k小≥mid，调整左边界；否则调整右边界； ④ 最终记录的合法mid即为第k小；

• 复杂度：$O(\log V \times \log^2 n)$（V是值域范围，如1e8则logV≈27）。

3. 内层Splay的关键设计（有序操作的效率保障）

1. 平衡维护：

   • 旋转（rotate）：将节点向上旋转一层，保持BST有序性；

   • Splay操作：将目标节点旋到根（双旋优化：方向不同先旋子节点，方向相同先旋父节点），避免树倾斜，保证操作效率$O(\log n)$；

2. 哨兵值（-INF/INF）： 避免空节点判断（如查询前驱时无需考虑左子树为空），简化边界处理；

3. 子树大小（siz）： 核心辅助字段，pushup函数（siz=左siz+右siz+1）必须在旋转/插入/删除后调用，否则排名计算错误；

4. 引用传递root： Splay的root必须用引用传递，否则插入/删除后根节点更新无法生效。

4. 复杂度与适用场景

操作	时间复杂度	适用场景
构建	$O(n \log^2 n)$
单点更新	$O(\log^2 n)$	1. 动态数组（支持单点更新）；2. 需频繁查询任意区间的排名、第k小、前驱/后继；3. 数据规模n,m≤5e4（log²n≈256，效率可接受）；4. 不适合静态数组（主席树更高效）。
区间排名/前驱/后继
区间第k小	$O(\log V \times \log^2 n)$

5. 核心避坑点

1. Splay的边界处理：必须插入-INF/INF哨兵，否则空节点会导致访问越界；

2. pushup时机：Splay的旋转、插入、删除后必须调用pushup更新siz，否则排名计算错误；

3. 结果合并逻辑：前驱取max、后继取min、排名累加，不能搞反；

4. 二分答案范围：需覆盖题目元素的值域（如代码中0~1e8），否则漏解；

5. 节点数组大小：Splay的节点数组需预留足够空间（如N×40），避免数组越界；

6. 编译器优化：需开启O2优化，否则Splay的常数会导致超时。

// 数据结构：线段树套Splay（树状结构嵌套）
// 核心功能：解决「动态数组」的区间第k小、区间排名、区间前驱/后继、单点更新问题
// 时间复杂度：预处理 O(n log²n)，单次操作 O(log²n)（线段树每层 O(logn) + Splay 操作 O(logn)）
// 适用场景：n,m ≤ 5e4，需支持动态修改元素，且频繁查询任意区间的排名/第k小/前驱后继
// 提醒：需开启 O2 优化（编译器优化后可显著提升 Splay 操作效率）
#include <bits/stdc++.h>
using namespace std;

#define N 50005                  // 原始数组最大长度（5e4，适配题目数据范围）
#define INF 2147483647           // 哨兵值（int最大值），用于Splay树边界处理（避免空节点判断）
#define ls(x) tr[x].s[0]         // 宏定义：x节点的左儿子（s[0]存储左子树索引）
#define rs(x) tr[x].s[1]         // 宏定义：x节点的右儿子（s[1]存储右子树索引）

// Splay树节点结构体（每个节点维护二叉搜索树+BST平衡特性）
struct node
{
    int s[2];   // s[0]左儿子、s[1]右儿子（0=左，1=右，便于位运算切换）
    int p;      // 父节点索引（0表示无父节点）
    int v;      // 节点存储的值（BST的排序依据：左子树<根<右子树）
    int siz;    // 以当前节点为根的子树大小（用于排名、第k小查询）

    // 节点初始化函数：给节点赋值父节点p1和值v1，子树大小初始为1
    void init(int p1, int v1)
    {
        p = p1;    // 父节点索引
        v = v1;    // 节点值
        siz = 1;   // 新节点仅自身，子树大小=1
    }
} tr[N * 40];  // Splay树节点数组（40是经验系数：线段树4层×Splay logn层，适配5e4数据）

int n, m;          // n：原始数组长度；m：查询/更新操作次数
int w[N];          // 原始数组（存储初始元素，支持单点更新）
int idx;           // Splay树节点计数器（动态分配节点索引，从1开始）

// 【Splay基础操作】更新子树大小（核心辅助函数）
// 当节点x的左右子树变化时，需通过左子树大小+右子树大小+1（自身）更新siz
inline void pushup(int x)
{
    tr[x].siz = tr[ls(x)].siz + tr[rs(x)].siz + 1;
}

// 【Splay核心操作】旋转（维持BST性质，调整树的平衡）
// 功能：将节点x向上旋转一层，成为父节点y的父节点，保持BST有序性
inline void rotate(int x)
{
    int y = tr[x].p;  // x的父节点y
    int z = tr[y].p;  // y的父节点z（祖父节点）
    int k = tr[y].s[1] == x;  // k=1表示x是y的右儿子，k=0表示x是y的左儿子

    // 步骤1：更新z的儿子（z的原儿子是y，现在改为x）
    tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;  // x的父节点改为z

    // 步骤2：处理x的异侧子树（x的k^1儿子（左→右，右→左）交给y作为k儿子）
    tr[y].s[k] = tr[x].s[k ^ 1];
    tr[tr[x].s[k ^ 1]].p = y;  // x的异侧子树父节点改为y

    // 步骤3：x成为y的父节点（y作为x的k^1儿子）
    tr[x].s[k ^ 1] = y;
    tr[y].p = x;  // y的父节点改为x

    pushup(y);  // 先更新y的子树大小（y的子树结构变化）
    pushup(x);  // 再更新x的子树大小（x的子树结构变化）
}

// 【Splay核心操作】Splay旋转（将x转到目标位置）
// root：Splay树的根节点（引用传递，可能更新根）
// x：要旋转的节点；k：目标父节点（0表示转到根节点）
inline void splay(int &root, int x, int k)
{
    // 循环：直到x的父节点是k（未到达目标位置）
    while (tr[x].p != k)
    {
        int y = tr[x].p;  // x的父节点y
        int z = tr[y].p;  // y的父节点z（祖父节点）
        if (z != k)  // 若祖父节点不是目标k，需判断旋转方向（双旋优化，维持树平衡）
        {
            // 若x和y的父子方向不同（x是y的右儿子，y是z的左儿子，或反之），先旋x
            if ((rs(y) == x) ^ (rs(z) == y)) rotate(x);
            else rotate(y);  // 方向相同，先旋y（双旋避免单旋导致的树倾斜）
        }
        rotate(x);  // 每次循环至少旋x一次，向目标位置靠近
    }
    if (!k) root = x;  // 若目标父节点是0（根节点），更新Splay树的根为x
}

// 【Splay业务操作】插入值v到Splay树
// root：Splay树的根（引用传递，插入后可能更新根）；v：待插入的值
inline void insert(int &root, int v)
{
    int u = root, p = 0;  // u：当前遍历节点；p：u的父节点（初始为0）
    // 步骤1：找到插入位置（BST性质：v>当前值走右子树，否则走左子树）
    while (u)
    {
        p = u;  // 记录父节点
        u = tr[u].s[v > tr[u].v];  // 决定走左/右子树（v>tr[u].v为1→右子树，0→左子树）
    }
    u = ++idx;  // 分配新节点索引
    tr[p].s[v > tr[p].v] = u;  // 父节点p的对应儿子设为新节点u
    tr[u].init(p, v);  // 初始化新节点（父节点p，值v）
    splay(root, u, 0);  // 将新节点u旋到根，维持Splay树平衡
}

// 【Splay业务操作】删除Splay树中值为v的节点（假设v存在）
// root：Splay树的根（引用传递，删除后可能更新根）；v：待删除的值
inline void del(int &root, int v)
{
    int u = root;  // u：当前遍历节点（从根开始）
    // 步骤1：找到值为v的节点u
    while (u)
    {
        if (tr[u].v == v) break;  // 找到目标节点，退出循环
        if (tr[u].v < v) u = rs(u);  // 当前值<v，走右子树
        else u = ls(u);  // 当前值>v，走左子树
    }
    splay(root, u, 0);  // 步骤2：将u旋到根，便于删除

    int l = ls(u), r = rs(u);  // l：u的左子树根；r：u的右子树根
    // 步骤3：找到左子树的最大值节点（左子树最右节点）
    while (rs(l)) l = rs(l);
    // 步骤4：找到右子树的最小值节点（右子树最左节点）
    while (ls(r)) r = ls(r);

    splay(root, l, 0);  // 步骤5：将左子树最大值l旋到根
    splay(root, r, l);  // 步骤6：将右子树最小值r旋到l的右儿子（此时u在l和r之间）
    ls(r) = 0;  // 步骤7：删除u（r的左儿子原本是u，设为0即断开连接）
    splay(root, r, 0);  // 步骤8：将r旋到根，更新树结构和子树大小
}

// 【Splay业务操作】查询值v在Splay树中的排名（排名=比v小的元素个数+1）
// root：Splay树的根；v：查询排名的值；返回值：比v小的元素个数
inline int getrank(int root, int v)
{
    int u = root, res = 0;  // u：当前遍历节点；res：记录比v小的元素个数
    while (u)
    {
        if (tr[u].v < v)  // 当前节点值<v，左子树全比v小，累加左子树大小+1（当前节点）
        {
            res += tr[ls(u)].siz + 1;
            u = rs(u);  // 继续向右子树查找（可能有更大的但仍<v的元素）
        }
        else u = ls(u);  // 当前节点值≥v，向左子树查找
    }
    return res;  // 返回比v小的元素个数（排名=res+1）
}

// 【Splay业务操作】查询Splay树中v的前驱（比v小的最大元素）
// root：Splay树的根；v：查询前驱的值；返回值：前驱（无则返回-INF）
inline int getpre(int root, int v)
{
    int u = root, res = -INF;  // res初始为-INF（无前驱时返回）
    while (u)
    {
        if (tr[u].v < v)  // 当前节点值<v，可能是前驱候选，更新res
        {
            res = tr[u].v;
            u = rs(u);  // 向右子树查找更大的候选（接近v的）
        }
        else u = ls(u);  // 当前节点值≥v，向左子树查找
    }
    return res;
}

// 【Splay业务操作】查询Splay树中v的后继（比v大的最小元素）
// root：Splay树的根；v：查询后继的值；返回值：后继（无则返回INF）
inline int getnxt(int root, int v)
{
    int u = root, res = INF;  // res初始为INF（无后继时返回）
    while (u)
    {
        if (tr[u].v > v)  // 当前节点值>v，可能是后继候选，更新res
        {
            res = tr[u].v;
            u = ls(u);  // 向左子树查找更小的候选（接近v的）
        }
        else u = rs(u);  // 当前节点值≤v，向右子树查找
    }
    return res;
}

////////// 以下是线段树部分（线段树的每个节点对应一棵Splay树）
#define lc u<<1  // 宏定义：线段树节点u的左儿子（u*2）
#define rc u<<1|1// 宏定义：线段树节点u的右儿子（u*2+1）
int root[N * 4];  // root[u]：线段树第u个节点对应的Splay树的根

// 【线段树操作】构建线段树（每个线段树节点的Splay树初始化）
// u：当前线段树节点索引；l, r：当前线段树节点覆盖的区间[1-based]
void build(int u, int l, int r)
{
    // 步骤1：给当前Splay树插入哨兵-INF和INF（避免边界处理时空节点判断）
    insert(root[u], -INF), insert(root[u], INF);
    // 步骤2：插入当前线段树区间[l, r]内的所有原始元素w[i]
    for (int i = l; i <= r; i++)
        insert(root[u], w[i]);
    if (l == r) return;  // 叶子节点（覆盖单个元素），构建结束
    int mid = l + r >> 1;  // 区间中点（位运算优化除法）
    build(lc, l, mid);     // 递归构建左子树（覆盖[l, mid]）
    build(rc, mid + 1, r); // 递归构建右子树（覆盖[mid+1, r]）
}

// 【线段树查询】查询区间[x, y]中值v的排名（排名=比v小的元素个数+1）
// u：当前线段树节点；l, r：当前线段树节点覆盖区间；x,y：查询区间；v：查询排名的值
int queryrank(int u, int l, int r, int x, int y, int v)
{
    // 情况1：当前线段树节点覆盖区间与查询区间无交集，返回0
    if (x <= l && r <= y)
        // 当前Splay树中比v小的元素个数 - 1（减去哨兵-INF的贡献）
        return getrank(root[u], v) - 1;
    int mid = l + r >> 1, res = 0;
    // 情况2：左子树与查询区间有交集，递归查询左子树
    if (x <= mid) res += queryrank(lc, l, mid, x, y, v);
    // 情况3：右子树与查询区间有交集，递归查询右子树
    if (y > mid) res += queryrank(rc, mid + 1, r, x, y, v);
    return res;  // 累加所有覆盖区间的结果，返回比v小的元素个数
}

// 【线段树查询】查询区间[x, y]中的第k小元素（二分答案+queryrank）
// u：线段树根节点；x,y：查询区间；k：目标排名（1-based）
int queryval(int u, int x, int y, int k)
{
    int l = 0, r = 1e8, ans;  // 二分答案的范围（根据题目数据值域设定）
    while (l <= r)
    {
        int mid = l + r >> 1;  // 二分中点（候选答案）
        // 查询区间[x,y]中比mid小的元素个数+1 ≤k → mid可能是第k小，尝试更大值
        if (queryrank(1, 1, n, x, y, mid) + 1 <= k)
        {
            l = mid + 1;
            ans = mid;  // 记录当前合法候选答案
        }
        else r = mid - 1;  // 候选答案太大，缩小范围
    }
    return ans;  // 返回第k小元素
}

// 【线段树更新】单点更新：将位置pos的值从w[pos]改为v
// u：当前线段树节点；l, r：当前线段树节点覆盖区间；pos：更新位置；v：新值
void change(int u, int l, int r, int pos, int v)
{
    // 步骤1：在当前线段树节点的Splay树中，删除旧值w[pos]，插入新值v
    del(root[u], w[pos]);
    insert(root[u], v);
    if (l == r) return;  // 叶子节点（仅覆盖pos），更新结束
    int mid = l + r >> 1;
    // 步骤2：递归更新左/右子树（根据pos位置）
    if (pos <= mid) change(lc, l, mid, pos, v);
    else change(rc, mid + 1, r, pos, v);
}

// 【线段树查询】查询区间[x, y]中v的前驱（比v小的最大元素）
// u：当前线段树节点；l, r：当前线段树节点覆盖区间；x,y：查询区间；v：查询前驱的值
int querypre(int u, int l, int r, int x, int y, int v)
{
    // 情况1：当前区间与查询区间无交集，返回-INF（无贡献）
    if (x <= l && r <= y)
        return getpre(root[u], v);
    int mid = l + r >> 1, res = -INF;
    // 情况2：左子树有交集，取左子树前驱的最大值
    if (x <= mid) res = max(res, querypre(lc, l, mid, x, y, v));
    // 情况3：右子树有交集，取右子树前驱的最大值
    if (y > mid) res = max(res, querypre(rc, mid + 1, r, x, y, v));
    return res;  // 返回区间内的最大前驱
}

// 【线段树查询】查询区间[x, y]中v的后继（比v大的最小元素）
// u：当前线段树节点；l, r：当前线段树节点覆盖区间；x,y：查询区间；v：查询后继的值
int querynxt(int u, int l, int r, int x, int y, int v)
{
    // 情况1：当前区间与查询区间无交集，返回INF（无贡献）
    if (x <= l && r <= y)
        return getnxt(root[u], v);
    int mid = l + r >> 1, res = INF;
    // 情况2：左子树有交集，取左子树后继的最小值
    if (x <= mid) res = min(res, querynxt(lc, l, mid, x, y, v));
    // 情况3：右子树有交集，取右子树后继的最小值
    if (y > mid) res = min(res, querynxt(rc, mid + 1, r, x, y, v));
    return res;  // 返回区间内的最小后继
}

int main()
{
    scanf("%d%d", &n, &m);  // 读取原始数组长度n和操作次数m
    // 读取原始数组w（1-based下标，适配线段树区间）
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    build(1, 1, n);  // 构建线段树（根节点1，覆盖区间[1, n]）

    while (m--)  // 处理m个操作（m--等价于处理完一次操作后m减1）
    {
        int op, x, y, v;
        scanf("%d", &op);  // 读取操作类型op
        // 操作3是单点更新（仅需位置x和新值v），其他操作是区间查询（需区间[x,y]和参数v）
        if (op == 3) scanf("%d%d", &x, &v);
        else scanf("%d%d%d", &x, &y, &v);

        if (op == 1)  // 操作1：查询区间[x,y]中v的排名（排名=比v小的个数+1）
            printf("%d\n", queryrank(1, 1, n, x, y, v) + 1);
        if (op == 2)  // 操作2：查询区间[x,y]中的第k小元素（v=k）
            printf("%d\n", queryval(1, x, y, v));
        if (op == 3)  // 操作3：单点更新（将位置x的值改为v，更新原始数组w[x]）
            change(1, 1, n, x, v), w[x] = v;
        if (op == 4)  // 操作4：查询区间[x,y]中v的前驱
            printf("%d\n", querypre(1, 1, n, x, y, v));
        if (op == 5)  // 操作5：查询区间[x,y]中v的后继
            printf("%d\n", querynxt(1, 1, n, x, y, v));
    }
    return 0;
}