一、主席樹和可持久化線段樹
主席樹和可持久化線段樹沒有區別。主席樹學名為可持久化線段樹,可以用來解決線段樹存儲歷史狀態的問題。我們在進行單點修改后,線段樹只有一條鏈節點被修改,可以讓修改后的樹與修改前的樹共享節點,節省時間空間。
應用:
查找一個區間的第k大的值;
查詢某個數的排名;
查詢整個數組的排序;
查詢前驅和后繼。
單點修改
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的元素個數,pos是要查找的位置
查詢區間中的數出現次數
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);
}//對單點查詢同樣適用
查詢所有數的第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小就減去左邊
查詢前驅(后繼同)
int findpre(int node,int start,int end){ //找這個區間目前最大的
??? 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的前驅
??? 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);? //在左區間尋找 } 延伸閱讀: 二、權值線段樹 線段樹的葉子節點保存的是當前值的個數。 每個節點保存區間左右端點以及所在區間節點的個數。 由于值域范圍通常較大,一般會配合離散化或動態開點等策略優化空間。