区间第k大值（带区间修改，可持久化线段树）

### 可持久化线段树解决带区间修改的区间第K大值问题

对于带有区间修改功能的可持久化线段树来求解区间第K大值问题，主要思路在于构建并维护一棵能够反映历史版本变化的线段树结构。这棵树不仅支持查询操作还允许对特定范围内的元素进行批量更新。

#### 构建初始数据结构

为了处理此类问题，首先需要准备输入数值列表，并对其进行预处理——即排序与去重操作[^1]：

vector<int> nums;
// 对nums执行sort和unique算法去除重复项...
auto end_unique = unique(nums.begin(), nums.end());
nums.erase(end_unique, nums.end());

上述代码片段展示了如何利用STL库函数`std::sort()`以及`std::unique()`完成这一过程。经过此步之后得到的是不含任何冗余信息的独特整数集合，这些将成为后续建立权值线段树的基础。

#### 创建基础版可持久化线段树

接下来创建一个空的线段树实例作为起点，在此基础上逐步加入原始序列中的各个元素形成新的版本。每当向其中添加一个新的数字时，实际上是在原有基础上复制出一条新路径而非直接更改旧有节点的数据；这样做可以确保每次变更都保留下来供将来回溯使用。

当面对具有区间修改需求的情况时，则需进一步扩展基本模型使之具备高效地处理连续范围内多个位置同步变动的能力。一种常见做法是采用懒惰传播（Lazy Propagation）机制配合动态开点策略减少不必要的内存消耗[^2]。

#### 实现懒惰标记下的区间修改

针对每一个可能被影响到的时间戳版本v及其对应子树root[v]，引入额外字段lazy[]用来存储尚未向下传递给子孙结点的信息量差额。具体来说就是在遇到涉及某一段落[l,r]内所有成员统一增减相同偏移量delta的情形下，只需简单设置相应根部节点处的标志位即可暂时搁置实际改动动作直到真正访问该部分为止。

以下是简化后的C++伪码表示法展示怎样在已有框架之上增加这项特性：

struct Node {
    int sum;      // 当前区间总和
    int lazy;     // 待应用至子节点的变化增量
};

void push_down(int v, int tl, int tr){
    if (tl != tr && node[v].lazy != 0) {
        int tm = (tl + tr) / 2;
        
        apply(node[left_child(v)], node[v].lazy);
        apply(node[right_child(v)], node[v].lazy);

        node[v].lazy = 0;
    }
}

void update_range(int &pv, int pv_old, int l, int r, int tl, int tr, int delta){
    if (!pv) { 
        clone_node(pv, pv_old); 
    }

    if (l > tr || r < tl) return;

    if (l <= tl && tr <= r){
        apply(node[pv], delta);
        return ;
    }

    int tm = (tl + tr) >> 1;
    
    push_down(pv, tl, tr);

    update_range(left_child(pv), left_child(pv_old), l, r, tl, tm, delta);
    update_range(right_child(pv), right_child(pv_old), l, r, tm+1, tr, delta);

    pull_up(pv);
}

这里定义了一个辅助方法`push_down()`负责将父级累积下来的延迟调整分发下去，而核心逻辑则由`update_range()`承载，它接受当前正在编辑的新版本索引、上一时刻的状态指针连同待作用域边界参数共同决定何时何地实施累加运算。

#### 查询指定时间片上的第K大数据

最后一步便是编写专门用于检索任意给定时间段内部满足条件的最大几个候选对象之一的功能模块。考虑到已经建立了完整的多世代存档体系，因此只需要沿着选定的历史轨迹追溯回去找到匹配的目标即可得出结论。