题目描述
如题，给定 n 个整数构成的序列 a，将对于指定的闭区间 [l, r] 查询其区间内的第 k 小值。
输入格式
第一行包含两个整数，分别表示序列的长度 n 和查询的个数 m。
第二行包含 n 个整数，第 i 个整数表示序列的第 i 个元素 ai
接下来 m 行每行包含三个整数 l, r, k 表示查询区间 [l, r]内的第 k 小值
直接上手模拟一组数据
7 1
1 5 2 6 3 7 4
2 5 3
1.首先建立基树
struct node {
int ls, rs;//表示左右子节点的下标
int cnt;//区间内数的个数，区间为数值上的区间
}tree[N << 5];
int root[N];//存放各个版本的根节点
int idx;//动态开点
int build(int l, int r) {//以数值区间建立一个基树,每个版本的线段树中节点都是一样的
int root = ++idx;
if (l == r) return root;
int mid = l + r >> 1;
tree[root].ls = build(l, mid);
tree[root].rs = build(mid + 1, r);
return root;// 返回该子树的根节点
}
通过结构体里的来ls，rs可以确定节点左右儿子的位置
又根据递归的性质节点所管辖的区间范围可确定
逐一插入数字，将每个数字的大小（即离散化后的编号）插入到它的位子上，然后并把所有包括它的区间的和标记都++
int modify(int old_root, int l, int r, int k) {//插入操作,增加一个数 root 为上一个的根节点。
int new_root = ++idx;//先创建一个新的根节点
tree[new_root] = tree[old_root];//每次修改前令本次的根为上一次的根，左右儿子的指向不变
if (l == r) {
tree[new_root].cnt++;//插入位置的个数++
return new_root;
}
int mid = l + r >> 1;
//更改左右儿子的指向，具体的来说不改的不变需要改的动态创建新节点(递归式)
if (k <= mid)tree[new_root].ls = modify(tree[old_root].ls, l, mid, k);
else tree[new_root].rs = modify(tree[old_root].rs, mid + 1, r, k);
tree[new_root].cnt = tree[tree[new_root].ls].cnt + tree[tree[new_root].rs].cnt;// 根据子节点给当前节点赋值
return new_root;
}
最后插入4时
接下来我们考虑查询。
要查询[2, 5]中第3大的数我们首先把第1棵线段树和第5棵拿出来
然后我们发现，将对应节点的数相减，刚刚好就是[2, 5]内某个范围内的数的个数。比如[1, 4]这个节点相减是2，就说明[2. 5]内有2个数是在1~4范围内（就是2, 3）。
所以对于一个区间[l, r]，我们可以每次算出在[l, mid]范围内的数，
如果数量<=k（k就是第k小），就往左子树走，否则就往右子树走
int query(int per_v, int next_v, int l, int r, int k) {// 查询操作
if (l == r) return l;
int cnt = tree[tree[per_v].ls].cnt - tree[tree[next_v].ls].cnt;// 通过区间减法得到左儿子的信息,求的时第k小所以在左边
int mid = l + r >> 1;
if (k <= cnt)return query(tree[per_v].ls, tree[next_v].ls, l, mid, k);// 说明在左儿子中
else return query(tree[per_v].rs, tree[next_v].rs, mid + 1, r, k - cnt);// 说明在右儿子中
}
注意以上将各个版本线段树拿出来讨论便于直观的理解理解其查询过程
实际的可持久化线段树是动态开点每次最多只需要logn的空间，具体的来说每次创建新的节点同原来的节点(左右儿子的指向也不变)然后再根据是否修改区间的值创建新节点更改左右儿子的指向
实际的样子：各个版本的线段树
P3834 【模板】可持久化线段树 2（主席树）
#include<bits/stdc++.h>
#include <unordered_map>
#include<algorithm>
using namespace std;
template<class...Args>
void debug(Args... args) {//Parameter pack
auto tmp = { (cout << args << ' ', 0)... };
cout << "\n";
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pll;
typedef pair<int, int>pii;
const ll N = 1e6 + 5;
const ll MOD = 998244353;
const ll INF = 0x7fffffff;
struct node {
int ls, rs;//表示左右子节点的下标
int cnt;//区间内数的个数，区间为数值上的区间
}tree[N << 5];
int root[N];//存放各个版本的根节点
int idx;//动态开点
int build(int l, int r) {//以数值区间建立一个基树,每个版本的线段树中节点都是一样的
int root = ++idx;
if (l == r) return root;
int mid = l + r >> 1;
tree[root].ls = build(l, mid);
tree[root].rs = build(mid + 1, r);
return root;// 返回该子树的根节点
}
int modify(int old_root, int l, int r, int k) {//插入操作,增加一个数 root 为上一个的根节点。
int new_root = ++idx;//先创建一个新的根节点
tree[new_root] = tree[old_root];//每次修改前令本次的根为上一次的根
if (l == r) {
tree[new_root].cnt++;//插入位置的个数++
return new_root;
}
int mid = l + r >> 1;
if (k <= mid)tree[new_root].ls = modify(tree[old_root].ls, l, mid, k);
else tree[new_root].rs = modify(tree[old_root].rs, mid + 1, r, k);
tree[new_root].cnt = tree[tree[new_root].ls].cnt + tree[tree[new_root].rs].cnt;// 根据子节点给当前节点赋值
return new_root;
}
int query(int per_v, int next_v, int l, int r, int k) {// 查询操作
if (l == r) return l;
int cnt = tree[tree[per_v].ls].cnt - tree[tree[next_v].ls].cnt;// 通过区间减法得到左儿子的信息
int mid = l + r >> 1;
if (k <= cnt)return query(tree[per_v].ls, tree[next_v].ls, l, mid, k);// 说明在左儿子中
else return query(tree[per_v].rs, tree[next_v].rs, mid + 1, r, k - cnt);// 说明在右儿子中
}
int a[N];
vector<int>nums;
int getid(int val) { // 离散化
return lower_bound(nums.begin(), nums.end(), val) - nums.begin();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
root[0] = build(0, nums.size() - 1);
for (int i = 1; i <= n; i++)root[i] = modify(root[i - 1], 0, nums.size() - 1, getid(a[i]));
while (m--) {
int l, r, k;
cin >> l >> r >> k;
cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << "\n";
}
return 0;
}