可持久化线段树学习笔记 (二)

简介

本期主要简单介绍可持久化权值线段树 (即主席树).

前置知识

1. 线段树
2. 权值线段树
3. 普通的可持久化线段树

可持久化权值线段树 (主席树)

主席树是一种把数字的值或离散化后的位置当作左右端点 (即权值线段树) 的可持久化权值线段树.

这里我们通过一道模板题 静态区间第k小 来讲解. 这道题我们可以以权值线段树为单个树建立可持久化线段树. 我们可以运用前缀和的思想, 对于 \( root_i \) 的节点 \( a_{j,k} \) 表示 1 到 i 的数中大小在离散化后的数组中 \( [k,k] \) 的数的个数. 这样我们可以在 \( \log n \) 的时间里求出一个区间的第 k 小.

code

const int MAXN = 200010;

struct node{
	int l,r,cnt;
}tree[15000000];
int root[MAXN];
int endd = 0;
int num[MAXN];
int bucket[MAXN];
int siz;
int n, m;
int clone(int id){
	tree[++endd] = tree[id];
	return endd;
}
void buildtree(int p, int l, int r){
	if(l == r) return;
	tree[p].l = ++endd;
	tree[p].r = ++endd;
	int m = (l + r) >> 1;
	buildtree(tree[p].l, l, m);
	buildtree(tree[p].r, m + 1, r);
	return;
}
int add(int p, int l, int r, int w){
	p = clone(p);
	++tree[p].cnt;
	if(l == r) return p;
	int m = (l + r) >> 1;
	if(w <= bucket[m]){
		tree[p].l = add(tree[p].l, l, m, w);
	}
	else{
		tree[p].r = add(tree[p].r, m + 1, r, w);
	}
	return p;
}
int ask(int p1, int p2,int l,int r, int k){
	if(l == r) return bucket[l];
	int m = (l + r) >> 1;
	if(k <= tree[tree[p2].l].cnt - tree[tree[p1].l].cnt) return ask(tree[p1].l, tree[p2].l, l, m, k);
	else return ask(tree[p1].r, tree[p2].r, m + 1, r, k - (tree[tree[p2].l].cnt - tree[tree[p1].l].cnt));
}
int main() {
	n = read(), m = read();
	rep(i,1,n){
		num[i] = read();
		bucket[i] = num[i];
	}
	sort(bucket + 1, bucket + 1 + n);
	rep(i,1,n){
		if(siz == 0 || bucket[i] > bucket[siz])
			bucket[++siz] = bucket[i];
		else 
			bucket[siz] = bucket[i];
	}
	buildtree(0,1,siz);
	rep(i,1,n){
		root[i] = add(root[i - 1], 1, siz, num[i]);
	}
	rep(i,1,m){
		int l = read(), r = read(), k = read();
		printf("%d\n", ask(root[l - 1], root[r], 1, siz, k));
	}
	return 0;
}