ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年6月2日 392点热度 2人点赞 0条评论

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

题目传送门: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;
}

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: acm C++ hjt树 主席树 可持久化线段树 洛谷 算法竞赛
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 什么是主席树?/ What is?
  • 新增节点 / Insert
  • 查询 / Query
  • 完整带注释代码 / Complete Code with Explain

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号