感想 入门即劝退 还有个动态主席树先弃坑了
这里贴点其他博客的关键字和解释
主席树的每个节点对应一颗线段树，此处有点抽象。在我们的印象中，每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息（信息视具体问题定）。对于一个待处理的序列a[1]、a[2]…a[n]，有n个前缀。每个前缀可以看做一棵线段树，共有n棵线段树；若不采用可持久化结构，带来的严重后果就是会MLE，即对内存来说很难承受。根据可持久化数据结构的定义，由于相邻线段树即前缀的公共部分很多，可以充分利用，达到优化目的，同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点信息，这些可能可能出现在根节点也可能出现在叶节点。
下面是某大牛的理解：所谓主席树呢，就是对原来的数列[1…n]的每一个前缀[1…i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1…i]中属于区间[L…R]的数一共有多少个（比如根节点是[1…n]，一共i个数，sum[root] = i；根节点的左儿子是[1…(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i…j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i…j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1…i]和[1…i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。
我的理解就低端点了 就是一直调用之前用的线段树 每次只改变我要用的那个链
这篇博客关于图的 讲解 来源https://blog.csdn.net/williamsun0122/article/details/77871278
具体建树方法建下图：
序列为 1 3 4 2
转的 一定要他们在sort后面的pos位置进树
同转的
比如有4个数5 3 6 9，求区间[2,4]第2小的数。
T[i]表示第i棵线段树的根节点编号，L[i]表示节点i的左子节点编号，R[i]表示节点i的右子节点编号，sum[i]表示节点i对应区间中数的个数。
我们先把序列离散化后是2 1 3 4。
我之前已经说了，主席树就是很多线段树的总体，而这些线段树就是按给定序列的所有前缀建立的。从T[0]开始建立空树，之后依次加入第i个数建立T[i]。
注意，如果我们直接以序列的所有前缀建立线段树肯定会MLE，这里主席树最精妙的地方就出来了。我们建立的这些线段树的结构，维护的区间是相同的，主席树充分利用了这些线段树中的相同部分，大大减少了空间消耗，达到优化目的。
直接上图，边看图边理解上面的话。
图中上面为用序列所有前缀建立的线段树，下面为所有线段树组合成主席树。
图中每个节点上面为节点编号，节点下面为对应区间，节点中数为区间中含有的数的个数，后面省略了区间。
从图中应该可以看出主席树是怎么充分利用这些线段树的相同结构来减少空间消耗的。当要新建一个线段树时最多只需要新增log2n个节点，相当于只更新了一条链，其它节点与它的前一个线段树公用。
建完主席树后我们看看它是怎么查找区间[2,4]第2小的数的。
首先我们要了解这些线段树是可加减的，比如我们要处理区间[l,r]，那么我们只需处理sum[T[r]]-sum[T[l-1]]就是给定序列的区间[l,r]中的数的个数。因为我们是按前缀处理的，这里看图自己体会一下。
这里我们要先计算res=sum[L[T[4]]]-sum[L[T[1]]]=1，即算出给定序列区间[2,4]中数的范围在区间[1,2]的数的个数，如果它的值大于k那么我们就应该从线段树的根节点走到左节点找第k个数，否则我们就应该从根节点到右节点找第k-res个数，之后递归下去直到叶子节点，返回叶子节点对应区间即为我们查找的数在离散化后序列中的下标。这里返回值为3，对应离散化后序列中数3，即原序列中数6。
讲到这里，静态的主席树就讲完了。我们算算时空复杂度。
设原序列有n个数，含有m次询问
空间复杂度：（建空树）4*n+（前缀和更新）nlog2
一般我们数组大小就开log2n、
时间复杂度：mlog2n
先画图 理解图 好理解
关键是对图的理解。。。 看懂图
方便 读代码 这份代码写了很多程序要注意的 已经解释
题目链接：http://poj.org/problem?id=2104
就是区间第K小 静态主席树板子
下面程序 数据不重复（然而并不清楚 重复数据怎么办 学习中）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
struct node{
int ls,rs;
int cnt;
}tree[maxn*20];// 主席树看起来蛮大的 orz相比写n堆线段树 小了不是太多
int cur,rt[maxn];
// 建树
int build(int l,int r){
int k=++cur;// 这里也可以写cnt++从0开始
tree[k].cnt=0;
if(l==r) return k;
int mid=(l+r)>>1;
tree[k].ls=build(l,mid);
tree[k].rs=build(mid+1,r);
return k;
}
// pre 继承上一个节点内容 rt[pre]就是 上一个头结点的位置
// 只改变 pos所在那个链 更新他在的ls或rs
// 每次都继承上一次的树 只改变 pos所在链 其他沿用 pre那个树
// 达成减少使用内存的目的
// orz 你fotile不亏是你主席 厉害厉害
int updata(int pre,int l,int r,int pos){
int k=++cur;
tree[k]=tree[pre];
if(l==pos&&r==pos){
tree[k].cnt++;
return k;
}
int mid=(l+r)>>1;
// cout<<k<<" "<<tree[k].ls<<" "<<tree[k].rs<<endl;
if(pos<=mid) tree[k].ls=updata(tree[k].ls,l,mid,pos);
else tree[k].rs=updata(tree[k].rs,mid+1,r,pos);
tree[k].cnt=tree[tree[k].ls].cnt+tree[tree[k].rs].cnt;
return k;
}
int query(int L,int R,int l,int r,int k){// L,R 数据的左右2端 l,r树中的位置
if(R==L) return L;
int mid=(L+R)>>1;
int th=tree[tree[r].ls].cnt-tree[tree[l].ls].cnt; // 前缀和思想 这样算区间有几个数据
if(k<=th) return query(L,mid,tree[l].ls,tree[r].ls,k); // k如果比TH小 就在这个区间
else return query(mid+1,R,tree[l].rs,tree[r].rs,k-th); // 不然就找 右儿子
}
int a[maxn];
int hasha[maxn];
int n,m,cnt,pos;
void init(){
cur=0;
cnt=0;
}
int main(){
while(cin>>n>>m){
init();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
hasha[i]=a[i];
}
sort(hasha+1,hasha+1+n);
cnt=unique(hasha+1,hasha+1+n)-hasha-1;
// 我们离散化后 建树
rt[0]=build(1,cnt);
// for(int i=0;i<20;i++){
// cout<<i<<" "<<tree[i].ls<<" "<<tree[i].rs<<endl;
// }
// 这里可以类比前缀和 update 不断将 a[i] 应该在的位置 放入主席树中
// 因为已经建好树了 找pos位置在i个线段树的位置 并将那个位置的CNT++;
// 这样查 特定区间的第K大值 只是在找 右端cnt-左端cnt == k 的数据在那里
// 查到时 肯定L==R
for(int i=1;i<=n;i++){
pos=lower_bound(hasha+1,hasha+1+cnt,a[i])-hasha;
rt[i]=updata(rt[i-1],1,cnt,pos);
}
// for(int i=0;i<20;i++){
// cout<<rt[i]<<" ";
// } cout<<endl;
// 这里返回是sort好以后的下标 其实也在告诉你
// 就是输入一堆数据大部分都是一个值 这个时候他也在新树中
// 唯一改变的就是 a[i]位置所在链 和对应链头结点cnt都+1
// 另外 理解一下 在主席树 图中 怎么看
// 2 1 4 3
// 1 2 位置 第1小数据 为什么是 1
// 第1个线段树 在 最底端 第2个位置+1
// 第2个线段树 在 最底端 第一个位置+1 其他继承上一个数(第二个数据在的链)
// 递归 去查 th==4第一次是大于k的 找左子树 l,r=(1,4)
// 第二次 th为2 同时k为1 还是找左子树 l,r=(1,2)
// 第3次 th为1 只能找右子树 返回id 1; l=1
// 同上 你信不信我其实直接coyp上面的没有改多少 orz
// 再看 1 2 位置第2小数据
// 第1个线段树 在 最底端 第2个位置+1
// 第2个线段树 在 最底端 第一个位置+1 其他继承上一个数(第二个数据在的链)
// 递归 去查 th==4第一次是大于k的 找左子树 l,r=(1,4)
// 第二次 th为2 同时k为2 还是找左子树 l,r=(1,2)
// 第3次 th为1 只能找右子树 返回id 2; l=r=2;
int pl,pr,kth,id;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&pl,&pr,&kth);
id=query(1,cnt,rt[pl-1],rt[pr],kth);
printf("%d\n",hasha[id]);
}
}
return 0;
}
2019 更新 好看点的代码。。
洛谷 https://www.luogu.org/problem/P3834
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, m;
int a[maxn], b[maxn], cnt;
struct node {
int lc, rc;
int cnt;
} tree[maxn * 20];
int tot, root[maxn];
int build(int l, int r) {
int p = ++ tot;
if(l == r) return p;
int mid = l + r >> 1;
tree[p].lc = build(l, mid);
tree[p].rc = build(mid + 1, r);
return p;
}
int ins(int now, int l, int r, int x) {
int p = ++ tot;
tree[p] = tree[now];
if(l == r) {
tree[p].cnt += 1;
return p;
}
int mid = l + r >> 1;
if(x <= mid) tree[p].lc = ins(tree[now].lc, l, mid, x);
else tree[p].rc = ins(tree[now].rc, mid + 1, r, x);
tree[p].cnt = tree[tree[p].lc].cnt + tree[tree[p].rc].cnt;
return p;
}
int ask(int p, int q, int l, int r, int L, int R, int k) {
if(l == r) return l;
int mid = l + r >> 1;
int th = tree[tree[p].lc].cnt - tree[tree[q].lc].cnt;
if(k <= th) return ask(tree[p].lc, tree[q].lc, l, mid, L, R, k);
else return ask(tree[p].rc, tree[q].rc, mid + 1, r, L, R, k - th);
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> a[i], b[i] = a[i];
sort(b + 1, b + 1 + n);
cnt = unique(b + 1, b + 1 + n) - b - 1;
root[0] = build(1, cnt);
for(int i = 1; i <= n; i ++) {
int pos = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
root[i] = ins(root[i - 1], 1, cnt, pos);
}
int l, r, k;
while(m --) {
cin >> l >> r >> k;
cout << b[ask(root[r], root[l - 1], 1, cnt, l, r, k)] << endl;
}
return 0;
}
京公网安备 11010502036488号