可持久化線段樹，即主席樹。

每次修改的時候不修改原來的節點，暴力建新節點，充分運用了函數式編程的思想。

模板題：給定一個數列，\(m\) 次詢問求區間 \([l,r]\) 內的第 \(k\) 大。

利用前綴和思想：

#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 5;struct node {int val;node *lchild, *rchild; } *rt[MAXN]; int a[MAXN], subA[MAXN], n, m, cnt = 0;node *newNode(int val, node *lc, node *rc) {node *ptr = new node;ptr->lchild = lc; ptr->rchild = rc; ptr->val = val;return ptr; }void build(node *&cur, int l, int r) {if(l < r) {cur = newNode(0, NULL, NULL);int mid = (l + r) >> 1;build(cur->lchild, l, mid);build(cur->rchild, mid + 1, r);} else cur = newNode(0, NULL, NULL); }void modify(node *&cur, node *fa, int l, int r, int x) {cur = newNode(fa->val + 1, fa->lchild, fa->rchild);if(l != r) {int mid = (l + r) >> 1;if(x <= mid) modify(cur->lchild, cur->lchild, l, mid, x);else modify(cur->rchild, cur->rchild, mid + 1, r, x);} }int query(node *u, node *v, int l, int r, int k) {if(l == r) return l;int mid = (l + r) >> 1, lessSize = v->lchild->val - u->lchild->val;if(lessSize >= k)return query(u->lchild, v->lchild, l, mid, k);else return query(u->rchild, v->rchild, mid + 1, r, k - lessSize); }int main() {scanf("%d%d", &n, &m);for(int i = 0; i < n; i++) {scanf("%d", a + i);subA[i] = a[i];}sort(subA, subA + n);int size = unique(subA, subA + n) - subA;for(int i = 0; i < n; i++)a[i] = lower_bound(subA, subA + size, a[i]) - subA + 1;build(rt[cnt++], 1, n);for(int i = 0; i < n; i++) {modify(rt[cnt], rt[cnt - 1], 1, n, a[i]);cnt++;}while(m--) {int x, y, k;scanf("%d%d%d", &x, &y, &k);printf("%d\n", subA[query(rt[x - 1], rt[y], 1, n, k) - 1]);}return 0; }

轉載于:https://www.cnblogs.com/zhylj/p/9903992.html

總結

以上是生活随笔為你收集整理的可持久化线段树学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。