【模板】可持久化線段樹

可持久化線段樹/主席樹：

顧名思義，該數據結構是可以訪問歷史版本的線段樹。用于解決需要查詢歷史信息的區間問題。

在功能與時間復雜度上與開n棵線段樹無異，然而空間復雜度從$O(n\times nlogn)$降到了$O(nlogn)$。

?

實現方法：

每次只更新有關的節點（每層一個，共$logn$個），其余節點不動。

用一個數組$rt[i]$記錄第$i$個版本線段樹的根節點（顯然每次必更新根節點）。

查詢時一路走下去，將兩個需要查詢的歷史版本的節點信息差分。

沒了。

?

模板題目：洛谷P3834

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>using namespace std;
#define MAXN 200005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long longinline int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}int N,M,Q,A[MAXN],B[MAXN],tot,rt[MAXN];
int ls[MAXN*20],rs[MAXN*20],sum[MAXN*20];inline void build(int l,int r,int &k){k=++tot;if(l==r) return;int mid=l+r>>1;build(l,mid,ls[k]);build(mid+1,r,rs[k]);
}inline void update(int l,int r,int p,int las,int &k){k=++tot; sum[k]=sum[las]+1;ls[k]=ls[las],rs[k]=rs[las];if(l==r) return;int mid=l+r>>1;if(p<=mid) update(l,mid,p,ls[las],ls[k]);else update(mid+1,r,p,rs[las],rs[k]);
} inline int query(int l,int r,int s,int u,int v){if(l==r) return l;int mid=l+r>>1,x=sum[ls[v]]-sum[ls[u]];if(s<=x) return query(l,mid,s,ls[u],ls[v]);else return query(mid+1,r,s-x,rs[u],rs[v]); 
}int main(){N=read(),Q=read();for(int i=1;i<=N;i++) A[i]=read();memcpy(B,A,sizeof(A));sort(B+1,B+1+N);M=unique(B+1,B+1+N)-B-1;build(1,M,rt[0]);for(int i=1;i<=N;i++){int p=lower_bound(B+1,B+1+M,A[i])-B;update(1,M,p,rt[i-1],rt[i]);}while(Q--){int l=read(),r=read(),k=read();printf("%d\n",B[query(1,M,k,rt[l-1],rt[r])]);}return 0;
}

?