淺談主席樹思想以及模板主席樹的原理主席樹的思想主席樹的應用主席樹的模板主席樹的題目
首先，作為一名蒟蒻，很早就聽說過主席樹這個高大上的名字，然而一直都不會（其實只是沒敲過代碼）。所以，今天就來正式的談一談主席樹，本蒻著此文以記之
它的原理十分簡單，就是想辦法把前后兩棵線段樹進行持久化并盡可能合并以節約空間。最后的空間復雜度大概是
然而這個時候它就會很自然地要求我們保證所有線段樹的結構均完全相同，這時我們可以通過建立一個參考序列，里面保存著區間，映射到主席樹里就是保存和這一區間有關的信息，然后對這個參考區間進行二分，這樣映射到每棵線段樹中它們的結構都將會是完全相同的
就我個人的理解，主席樹的本質，其實就是一顆可持久化線段樹。但是本來一顆好好的線段樹，我們為什么要把他們造成可持久化的呢，這是因為我們想訪問多個區間或多個子線段樹。此處的意思是我們建立一顆普通的線段樹時，我們只是使這棵線段樹對應了一個區間[
作為一名蒟蒻，我做的題非常少，對于這種神奇的數據結構，應用可能有求某段區間中第K大值或者是求某段區間中某個或某段數字的出現次數等等，此處留坑待補
下面的這個模板的功能是求某段區間第K小的值（當然是用主席樹實現的），代碼巨丑，不喜勿噴
#include<cstdlib>#include<cstdio>#include<algorithm>#define maxn 100005#define Pii pair<int,int>#define Author Goseqhusing namespace std;typedef struct node{ int sum; node* left; node* right; node(int sum){ this->sum=sum; right=left=NULL; } node():sum(0),left(NULL),right(NULL){}}node;//主席樹的結點node* list[maxn];node* op;node* op2;Pii line[maxn];Pii sline[maxn];//排序之后的line數組（參考區間）int n,m,a,b,c;void insert(int l,int r,int o,int i){ if(l==r) return; int m=(r-l)/2+l; if(line[i]>sline[m]){ op->left=op2->left; node* k=new node(op2->right->sum+1); op->right=k,op=k,op2=op2->right; insert(m+1,r,o*2+1,i); } else{ op->right=op2->right; node* k=new node(op2->left->sum+1); op->left=k,op=k,op2=op2->left; insert(l,m,o*2,i); } return;}//主席樹的二分插值過程/*void init2(int l,int r,int x,node* now){ if(l==r) return; int m=(r-l)/2+l; if(x>sline[m]){ node* now->left=new node(0); node* now->right=new node(1); } else{ node* now->left=new node(1); node* now->right=new node(0); } init2(l,m,x,now->left); init2(m+1,r,x,now->right); return;}*///此處對應了另一種實現，即以第一棵有意義的線段樹作為開頭void init2(int l,int r,node* now){ if(l==r)return; int m=(r-l)/2+l; now->left=new node(); now->right=new node(); init2(l,m,now->left); init2(m+1,r,now->right); return;}//這里是用一棵虛擬的線段樹作為開頭,感覺更加簡潔不易出錯void init(){ //init2(1,n,line[1],list[1]); list[0]=new node(); init2(1,n,list[0]); for(int i=1;i<=n;i++){ op=list[i]=new node(),op2=list[i-1]; insert(1,n,1,i); } return;}int query(int l,int r){ if(l==r) return sline[l].first; int con=op2->left->sum-op->left->sum; int m=(r-l)/2+l; if(c>con){ c-=con; op=op->right,op2=op2->right; return query(m+1,r); } else{ op=op->left,op2=op2->left; return query(l,m); }}//詢問過程int main(){ /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&line[i].first); line[i].second=i; sline[i]=line[i]; } sort(sline+1,sline+n+1); init(); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); op=list[a-1],op2=list[b]; 主席樹的題目這就等著其他的博文來進行補充啦O(∩_∩)O~
新聞熱點
疑難解答
