一、主席樹和可持久化線段樹

主席樹和可持久化線段樹沒有區(qū)別。主席樹學(xué)名為可持久化線段樹，可以用來解決線段樹存儲歷史狀態(tài)的問題。我們在進(jìn)行單點修改后，線段樹只有一條鏈節(jié)點被修改，可以讓修改后的樹與修改前的樹共享節(jié)點，節(jié)省時間空間。

應(yīng)用：

查找一個區(qū)間的第k大的值；

查詢某個數(shù)的排名；

查詢整個數(shù)組的排序；

查詢前驅(qū)和后繼。

單點修改

void update(int node,int start,int end,int pos){

??? if(start==end) tr[node]++;

??? else{

??????? int mid=start+end>>1;

??????? if(pos<=mid) update(node<<1,start,mid,pos);

??????? else update(node<<1|1,mid+1,end,pos);

??? }

}//tr[i]表示值為i的元素個數(shù),pos是要查找的位置

查詢區(qū)間中的數(shù)出現(xiàn)次數(shù)

int query(int node,int start,int end,int ql,int qr){

??? if(start==ql&&end==qr) return tr[node];

??? int mid=start+end>>1;

??? if(qr<=mid) return query(node<<1,start,mid,ql,qr);

??? else if(ql>mid) return query(node<<1|1,mid+1,end,ql,qr);

??? else return query(node<<1,start,mid,ql,qr)+query(node<<1|1,mid+1,end,ql,qr);

}//對單點查詢同樣適用

查詢所有數(shù)的第k大值

int kth(int node,int start,int end,int k){

??? if(start==end) return start;

??? int mid=start+end>>1;

??? int s1=tr[node<<1],s2=tree[node<<1|1];

??? if(k<=s2) return kth(node<<2|1,mid+1,end,k);

??? else return kth(node<<1,start,mid,k-s2);

} //注意是第k大，從右邊開始減，如果是第k小就減去左邊

查詢前驅(qū)(后繼同）

int findpre(int node,int start,int end){ //找這個區(qū)間目前最大的

??? if(start==end) return start; //找到直接返回

??? int mid=start+end>>1;

??? if(t[node<<1|1]) return findpre(node<<1|1,mid+1,end);

??? return findpre(node<<1,start,mid);

}

int pre(int node,int l,int r,int pos){ //求pos的前驅(qū)

??? if(r

??????? if(t[node]) return findpre(node,l,r);

??????? return 0;

??? }

??? int mid=l+r>>1,res;

??? if(mid+1

??? return pre(node<<1,l,mid,pos);? //在左區(qū)間尋找

}

延伸閱讀：

二、權(quán)值線段樹

線段樹的葉子節(jié)點保存的是當(dāng)前值的個數(shù)。

每個節(jié)點保存區(qū)間左右端點以及所在區(qū)間節(jié)點的個數(shù)。

由于值域范圍通常較大，一般會配合離散化或動態(tài)開點等策略優(yōu)化空間。