id="可持久化线段树主席树">可持久化线段树(主席树)

1.主席树是可以留存历史版本的线段树并且节省空间

操作：一般如果该节点的其中一个子树内容不变，可以直接指引到历史版本的内容，节省重新建立导致新开辟的空间，用模板题来讲解代码

id="给定-n-个整数构成的序列-a将对于指定的闭区间-lr-查询其区间内的第-k-小值">给定

[l,r]

“权值线段树就是对一个值域上值的个数进行维护的线段树”原视频09:51

回归正题，已经知道了权值线段树，本题可以利用权值线段树先建树，后递归查询，如果$

[l,(l+r)/2]

class="language-cpp">cin>>n>>m;

for(int

i=1;i<=n;i++){cin>>a[i];v.push_back(a[i]);

v.erase(unique(v.begin(),v.end()),v.end());

lower_bound(v.begin(),v.end(),x)-v.begin()+1;

void

p){hjt[++cnt]=hjt[pre];now=cnt;hjt[now].sum++;if(l==r)return;int

mid=(l+r)>>1;if(p<=mid)insert(l,mid,hjt[pre].l,hjt[now].l,p);else

insert(mid+1,r,hjt[pre].r,hjt[now].r,p);

//main函数内部

i=1;i<=n;i++){insert(1,n,root[i-1],root[i],getid(a[i]));

函数先复制上一个版本的线段树由于只是单点修改所以修改范围不大，后续进行修改即可，并且

now

tmp=hjt[hjt[r].l].sum-hjt[hjt[l].l].sum;if(k<=tmp)return

query(ln,mid,hjt[l].l,hjt[r].l,k);else

return

query(mid+1,rn,hjt[l].r,hjt[r].r,k-tmp);

//main函数内部

l,r,k;cin>>l>>r>>k;cout<<v[query(1,n,root[l-1],root[r],k)-1]<<"\n";

}

说明第k小就在左子树，反之在右子树，进行递归并返回(注:参数里

l-1

tmp=hjt[hjt[r].l].sum-hjt[hjt[l].l].sum

hjt[r].l是[1,r]数列中[1,中间值]的个数

hjt[l].l是[1,l]数列中[1,中间值]的个数

综合起来就是[l+1,r]数列中[1,中间值]的个数