洛谷P3834 【主席树模板】可持久化线段树 2

发布于 2022-06-02  558 次阅读


声明:本文中出现的“主席”二字仅为计算机领域一种数据结构的别名,请勿过度解读。

题目传送门:P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意请看原题链接。

最近在学习主席树,用这篇文章做一个总结。

什么是主席树?/ What is?

主席树是由黄嘉泰dalao改进得到的,因为名字的首字母为HJT,故名主席树(猜测)。

从概念上讲,主席树是线段树的一种延伸

但是通俗的说,主席树就是“对线段树的前缀和”。经常和权值线段树,又名可持久化权值线段树。

新增节点 / Insert

数组中每新增一个点,主席树就要多出logN个点来形成一条新的链并连接到之前的树中,共用相同的部分,新增的部分与后面的新增的树共用。

图片来自网络

上图中橙色的为“历史节点”,右边新增的蓝色的为“新增节点”。

主席树的一个节点需要将儿子的下标记录下来。用一个结构体表示为:

struct Node{int ls, rs, v;}

类似前缀和地,每次新增一条链,都会先将之前的链的信息复制到当前的链(包括左右儿子和权值),如果需要修改就修改,不用修改就让他去吧。

每次insert操作,需要用到当前树的根(利用&o变量自动新建一个),上一棵树的根(已经算出了),新增的数字x,区间1~N。

这里insert的x是下标(index),并不是值(value),表达的含义是数字x的数量+1。

insert函数完整版如下:

void insert(int &o, int pre, int x, int s = 1,int e = N)
{
	if(x < s || e < x)return;//递归出口,如果当前区间[s, e]和x无关就跳出 
	o = ++ idx;//分配一个节点给o,这个o引用类型会传给上一个点的ls或者rs 
	t[o] = t[pre];//将信息完全复制 
	t[o].v ++;//表示在这个节点下的区间中,多了1个数字 x 
	if(s == e)return;//到叶子节点就跳出 
	int mid = (s + e) / 2;//递归处理左右子树 
	insert(t[o].ls, t[pre].ls, x, s, mid);
	insert(t[o].rs, t[pre].rs, x,mid+1,e);
}

值得注意的是,主席树只能单点修改,区间查询。

查询 / Query

查询结果为元素权值大小位于区间[l, r]中个数。

这里要求第k小的数字。

每次算出左子树有多少个元素(left_sum),如果>=k,那么答案肯定在左子树,如果<k,答案肯定在右子树,注意递归右子树时,不能再找第k小的,应该找右子树中第k - left_sum小的。

int query(int lnode,int rnode,int k,int s = 1,int e = N)
{
	if(s == e)return s;//如果到了叶子节点,说明找到了我们要的值(在离散化数组中的下标) 
	int mid = (s + e) / 2;
	//计算左子树中元素个数 
	int left_sum = t[t[rnode].ls].v - t[t[lnode].ls].v; 
	if(left_sum >= k)//如果左子树的元素个数大于等于k说明答案肯定在左子树中 
		return query(t[lnode].ls, t[rnode].ls, k, s,  mid);
	return query(t[lnode].rs, t[rnode].rs, k - left_sum,mid+1,e);
}

完整带注释代码 / Complete Code with Explain

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int root[maxn], idx = 0, N, M, a[maxn];
struct Node{int ls, rs, v;}t[maxn << 6];
vector<int> v;

void insert(int &o, int pre, int x, int s = 1,int e = N)
{
	if(x < s || e < x)return;//递归出口,如果当前区间[s, e]和x无关就跳出 
	o = ++ idx;//分配一个节点给o,这个o引用类型会传给上一个点的ls或者rs 
	t[o] = t[pre];//将信息完全复制 
	t[o].v ++;//表示在这个节点下的区间中,多了1个数字 x 
	if(s == e)return;//到叶子节点就跳出 
	int mid = (s + e) / 2;//递归处理左右子树 
	insert(t[o].ls, t[pre].ls, x, s, mid);
	insert(t[o].rs, t[pre].rs, x,mid+1,e);
}

int query(int lnode,int rnode,int k,int s = 1,int e = N)
{
	if(s == e)return s;//如果到了叶子节点,说明找到了我们要的值(在离散化数组中的下标) 
	int mid = (s + e) / 2;
	//计算左子树中元素个数 
	int left_sum = t[t[rnode].ls].v - t[t[lnode].ls].v; 
	if(left_sum >= k)//如果左子树的元素个数大于等于k说明答案肯定在左子树中 
		return query(t[lnode].ls, t[rnode].ls, k, s,  mid);
	return query(t[lnode].rs, t[rnode].rs, k - left_sum,mid+1,e);
}

signed main()
{
	scanf("%lld %lld", &N, &M);	
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld", a + i);
		v.push_back(a[i]);
	}
	sort(begin(v), end(v));//离散化,用排序后的位置表示某个数字 
	for(int i = 1;i <= N; ++ i)
		insert(root[i], root[i - 1], lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1);
	//注意这里要+1,与a数组保持一致化 
	while(M --)
	{
		int l, r, k;scanf("%lld %lld %lld", &l, &r, &k);
		printf("%lld\n",v[query(root[l - 1], root[r], k, 1, N) - 1]);
		//因为前面的数字+1,所以这里需要-1来访问v中的对应下标的元素 
	}
	return 0;
}