有一個序列
,有 筆詢問,詢問有兩種:
- 把
加上 - 求
總和
像這樣有修改有查詢的問題,就需要用上線段樹了。
用把區間分割的方式去想,整個序列是一個大區間,然後這一個區間可以二等分成兩個小區間(如果長度是奇數,就看你喜歡放哪一邊),每一小區間又可以再二等分,這樣一直二等分下去,到最後會分到每一區間都剩下一個元素。先把這樣分出來的每個區間中的答案(所有會被詢問的資訊)算出來,詢問的時候在把一些區間合併。
這樣可以畫成一棵二元樹:根節點表示整個序列,它的左子節點表示它的左半部,右子節點表示它的右半部,然後每個節點的左子節點都表示該節點所表示範圍的左半部,右子節點表示右半部,葉節點則表示只有一個元素的區間。如此一來,每一個節點都表示一個區間,而每個節點表示的區間都完整包含了其子節點所表示的區間。
舉例來說,這是一個長度為
順帶一提,序列 index 要從
在每一個節點上,儲存在那個區間中我們想要的答案,例如最大值、最小值、區間和……等等的,然後父節點的答案可以從兩個子節點來得到,而每個葉節點所表示的區間中都只有一個數字,所以葉節點的答案只要考慮那個數字就好。
接著來討論一下線段樹該如何儲存,線段樹是一個接近完全二元樹的樹,所以可以用和完全二元樹一樣的方式存,也叫陣列型線段樹。完全二元樹是除了最深那層外每一層都全滿、最深那層的結點都靠右的樹,然後節點由淺至深、由左至右編號為 0、1、2……,這樣一來,節點
雖然它並不真的是完全二元樹,但其實不會浪費太多空間。來想一下陣列該開多大,也就是節點編號最多會用到多少。一棵有
如果
有時候節點資訊會有很多,像是在打懶標的時候,可以用 struct 包節點資訊。
除了用這種存法外,也可以用指標的存法,可以放在 struct 裡,例如: 1
2
3
4struct Node{
Node *l, *r; // 子節點指標
// 節點資訊 ...
};
還有一種我很喜歡的作法,我把它叫偽指標,就是用一個陣列當作 memory pool,把在陣列上的位置當成指標: 1
2
3
4
5
6struct Node{
int l, r; // 子節點編號
// 節點資訊 ...
};
vector<Node> st; // memory pool
int pos = 0; // memory pool 用到哪了
指標型線段樹用的空間,也就是線段樹的節點數是剛好
不過要注意指標型線段樹的空間不一定比較省,因為會多用兩個指標的空間,也就是 8 bit,所以在本來節點大小不大的狀況,陣列型的空間還是會用比較少。
在用指標型線段樹的時候,可以讓 build()
回傳新建的節點的指標,然後直接寫 1
2目前節點的左子節點 = build(左子節點);
目前節點的右子節點 = build(右子節點);modify
回傳節點的指標。
建立一棵線段樹很簡單,就一直遞迴去把區間二等分填數字就好。
為了方便,以下都使用 pseudo code。
1 | array a; // 序列初始值 |
複雜度就和節點數一樣,是
修改一個位置的時候,會改到所有包含它的區間,而這些區間就是「表示它的葉節點」和這個點的所有祖先,可以用遞迴的方式處理:
1 | // 節點 v 的區間範圍是 [L,R],要修改的地方是 pos,新值是 value |
線段樹的深度最深就是
如果遇到有一個節點的範圍被完整包含在查詢範圍內,就可以直接取這個節點記錄的答案,而不用往下找。這也可以用遞迴來做:
1 | // 查詢範圍是 [l,r],節點 v 的區間範圍是 [L,R] |
舉例來說,如果查詢區間是
(示意圖)
可以發現這數量最多就深度的四倍而已,所以複雜度也是
要做區間修改的話,可以用到懶人標記(可以參加分塊法的懶人標記),作法就是如果某個節點的區間被修改的區間完全包含,那麼就先在這個節點上記錄「整個節點的區間都被做了同樣的修改」,並且直接終止,而不再遞迴下去。至於打了懶人標記的節點,這個區間的答案要可以用懶人標記和原本的答案算出來。節點上要記錄原本的答案和懶人標記,至於真正的答案可以多寫一個 function 來算。
在詢問的時候,遇到有懶人標記的節點,要再往它的子節點走時,必須先把懶人標記下推,這樣在子節點算的答案才會是對的。在修改沒有交換律的時候(也就是修改順序不能改變,例如區間改值沒有交換律,而區間加值有交換律),之後的修改經過有懶人標記的節點,也要把懶人標記往下推,才能確保修改的順序是正確的。
下推的時候,先對子節點打懶標,然後再把這個節點記錄的答案變成真正的答案,例如:
1 | void push(vertex v){ |
遞迴的方式和區間詢問相同,概念是一樣的,也是「將修改的區間變成
1 | //新值是 value,修改區間是 [l,r],節點 v 的範圍是 [L,R] |
含懶標的區間查詢: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 查詢範圍是 [l,r],節點 v 的區間範圍是 [L,R]
type query(int l, int r, int L, int R, vertex v){
if(l == L && r == R)
return ans of v;
把節點v的懶標下推; // <----
int M = (L + R) / 2;
if(r <= M)
return query(l, r, L, M, v的左子節點);
else if(l > M)
return query(l, r, M + 1, R, v的右子節點);
else{
return 用query(l, M, L, M, v的左子節點)
和query(M + 1, r, M + 1, R, v的右子節點)
得出區間[l,r]的答案;
}
}
這樣一來,區間修改的複雜度就和區間查詢一樣,是
這是一個支援區間加值、區間詢問和的陣列型線段樹:
1 | struct Node{ |
有一個長度是
的序列,一開始裡面的元素都是 ,有 筆操作,每一個操作是以下其中兩種:
- 把
之間的值都加上 - 詢問
的區間和
像這種範圍超大的狀況,直接開線段樹會 MLE,這時候有兩種作法,第一種是離散化,也就是只管會用到的位置,第二種就是動態開點線段樹。
在這種狀況中,其實有很多節點是沒用的,可以不要把它們開出來,浪費記憶體空間,這個時候必須用指標型線段樹,偽指標也可以用,不過用偽指標線段樹的話,要先把空間開好,空間的用量大約是
實作的部分可以像前面偽指標線段樹讓 build()
回傳偽指標一樣,也可以讓 modify()
回傳節點指標。
指標版實作範例:
1 | struct Node{ |