声明:本文中出现的“主席”二字仅为计算机领域一种数据结构的别名,请勿过度解读。
题目传送门: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; }
文章评论