算法学习：主席树（可持久化线段树）

【前置知识】

 线段树

 

---

 

【定义】

【可持久化】能够保存历史版本，方便操作区间等，减少复杂度

 

 

 

---

【主席树】

  可解决的经典问题区间第k大/小

  时空复杂度为O(nlogn)

 

 

---

 

【模板题】

【luogu 3834】 

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 200010; const int MAXM = 200010; int l[MAXN], a[MAXN],T[MAXN]; int sum[21*MAXN], ls[21 * MAXN], rs[21 * MAXN]; int n, m; int cnt; int build(int l, int r) {int root=++cnt;sum[root] = 0;int mid = (l + r) >> 1;if (l < r){ls[root] = build(l, mid);rs[root] = build(mid + 1, r);}return root; } int update(int pre, int l, int r,int x) {int root=++cnt;sum[root] = sum[pre] + 1;ls[root] = ls[pre];rs[root] = rs[pre];int mid = (l + r) >> 1;if (l < r){if (x <= mid)ls[root] = update(ls[pre], l, mid, x);elsers[root] = update(rs[pre], mid + 1, r,x);}return root; } int query(int l,int r,int x, int y, int num) {if (l >= r)return l;int t = sum[ls[y]] - sum[ls[x]];int mid = (l + r) >> 1;if (num > t)return query(mid + 1, r, rs[x], rs[y], num - t);elsereturn query(l, mid, ls[x], ls[y], num);} int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);l[i] = a[i];}sort(l + 1, l + 1 + n);int maxn = unique(l + 1, l + 1 + n) - l - 1;T[0] = build(1, maxn);for (int i = 1; i <= n; i++){int t = lower_bound(l + 1, l + 1 + maxn,a[i]) - l;T[i] = update(T[i - 1], 1, maxn,t);}for (int i = 1; i <= m; i++){int x, y,k;scanf("%d%d%d", &x, &y, &k);printf("%d\n", l[query(1,maxn,T[x-1],T[y],k)]);}return 0; } View Code

 

转载于:https://www.cnblogs.com/rentu/p/11279963.html

总结

以上是生活随笔为你收集整理的算法学习：主席树（可持久化线段树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。