主席树模板

• 2018-03-04
• 0
• 0

主席树，顾名思义就是 fotile96 -- hjt 主席发明的一种数据结构。

本质上是一棵可持久化权值线段树（等价于可持久化 Trie），可以用来方便地求解许多支持单点修改的静态区间问题。

首先考虑直接对权值线段树上每次修改建立一个新版本，我们会发现这样无论是时间还是空间复杂度都无法承受。

由于单点修改只会对一条链造成影响，我们可以只新建这条链上的节点，其他节点与历史版本共用即可。

这样处理的时间和空间复杂度都是一个 log 级别的。

模板题：【模板】可持久化线段树 1（主席树）。

Code: O((N+M)logN) [41832KB, 868MS]

// 主席树 (2018.3.4)
// 洛谷 3834 【模板】可持久化线段树 1（主席树）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 200005
#define MAXNODE 3600005
using namespace std;

inline void getint(int &num){
	char ch; bool neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
	if(neg) num = -num;
}

int N, M, a[MAXN], disc[MAXN];
int rt[MAXN], sz[MAXNODE], lc[MAXNODE], rc[MAXNODE];
	
inline int newNode(int s, int l, int r){
	static int topp = 0;
	sz[++topp] = s, lc[topp] = l, rc[topp] = r;
	return topp;
}

inline int build(int l, int r){
	int u = newNode(0, 0, 0);
	if(l == r) return u;
	int mid = l + r >> 1;
	if(l <= mid) lc[u] = build(l, mid);
	if(mid < r) rc[u] = build(mid + 1, r);
	return u;
}

inline void add(int &u, int pred, int l, int r, int v){
	u = newNode(sz[pred] + 1, lc[pred], rc[pred]);
	if(l == r) return;
	int mid = l + r >> 1;
	if(v <= mid) add(lc[u], lc[pred], l, mid, v);
	else add(rc[u], rc[pred], mid + 1, r, v);
}

inline int query(int tot, int del, int l, int r, int k){
	if(l == r) return l;
	int mid = l + r >> 1, cnt = sz[lc[tot]] - sz[lc[del]];
	if(k <= cnt) return query(lc[tot], lc[del], l, mid, k);
	else return query(rc[tot], rc[del], mid + 1, r, k - cnt);
}

int main(){
	getint(N), getint(M);
	for(register int i = 1; i <= N; i++) getint(a[i]), disc[i] = a[i];
	sort(disc + 1, disc + N + 1);
	int K = unique(disc + 1, disc + N + 1) - disc - 1;
	for(register int i = 1; i <= N; i++) a[i] = lower_bound(disc + 1, disc + K + 1, a[i]) - disc;
	rt[0] = build(1, K);
	for(register int i = 1; i <= N; i++) add(rt[i], rt[i - 1], 1, K, a[i]);
	for(register int i = 1; i <= M; i++){
		int l, r, k; getint(l), getint(r), getint(k);
		int res = query(rt[r], rt[l - 1], 1, K, k);
		printf("%d\n", disc[res]);
	}
	return 0;
}