国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 主席樹和可持久化線段樹有什么區別?

主席樹和可持久化線段樹有什么區別?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 02:46:20 1696963580

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

主席樹和可持久化線段樹沒有區別。主席樹學名為可持久化線段樹,可以用來解決線段樹存儲歷史狀態的問題。我們在進行單點修改后,線段樹只有一條鏈節點被修改,可以讓修改后的樹與修改前的樹共享節點,節省時間空間。

應用:

查找一個區間的第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);? //在左區間尋找

}

延伸閱讀:

二、權值線段樹

線段樹的葉子節點保存的是當前值的個數。

每個節點保存區間左右端點以及所在區間節點的個數。

由于值域范圍通常較大,一般會配合離散化或動態開點等策略優化空間。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT