演算法知識 - Segment Tree 線段樹

演算法知識
字數統計： 3.3k   |   閱讀時間≈ 13分鐘

Segment Tree 線段樹 介紹

線段樹是一種二元樹型態的資料結構，通常用於需要大量查詢區間的問題，空間複雜度是 \(O(n)\)，查詢的時間複雜度則是 \(O(log \ n + k\)，k 為符合條件的區間數量

這種資料結構也能夠擴展到高維度

線段樹 - wiki

Segment Tree 線段樹 原理

先透過一張圖進行解釋，這就是線段樹的原貌

師大附中校隊 hackmd 提供，如不願讓我使用請通知我

為了方便好寫，通常我會將線段樹的區間設定為 \([1, n]\)，而非從零開始，但其實從零開始也可以實作成功。

線段樹一開始都會先到 root，之後根據我們所要查詢的區間往那方向進行查詢。

舉例，查詢 \([3, 5]\)

  • 先查詢 \([0, 8]\)，向下找 \([0, 4]\)、\([5, 8]\)
    • \([0, 4]\)，找 \([3, 4]\)，另外一邊則不再我們的查詢區間
      • \([3, 4]\) 是在我們查詢的區間，不再往下查詢，直接回傳此答案
    • \([5, 8]\)，查找 \([5, 6]\)，另外一邊則不再我們的查詢區間
      • \([5, 6]\) 查詢 \([5, 5]\)，另外一邊則不再我們的查詢區間
        • \([5, 5]\) 是在我們查詢的區間，不再往下查詢，直接回傳此答案
    • 將前面兩個回傳的查詢，進行比較，取出最大 or 最小值，然後輸出。

主要就是線段樹的查詢過程

結構型態

線段樹的每個節點必須要有三個值，左邊邊界、右邊邊界、儲存的值。

需要值得注意的是，由於線段樹的底層是一顆二元樹，因此大小絕對不能只開一樣大，必須要開到 \(4 * n\)，至於為甚麼要開 \(4 * n\)，以下進行證明。

  • 一顆二元樹的葉節點假如是 \(2_i\)，\(i\) 為負整數
  • 因此這棵樹所有節點不會大於 \(2^{i+1}\)，此證明如下
    • 第一層的節點是 1
    • 第二層節點是第二層的兩倍，之後以此類推
    • 得出公式 \(\sum_{i = 0}^{h-1} 2^i = 2^h-1\)，其中 h 為最大的深度，h-1 就表示非葉節點的最大深度
    • 一個最簡單的證明就是 2 進位的 \(111_{(2)}\) 不會大於 \(1000_{(2)}\)，且\(1000_{(2)} - 1 = 111_{(2)}\)
  • 因此二元樹總節點會是 \(2^{h}-1 + 2^h\)，化簡後就是 \(2^{h+1} -1\)

證明參考

資料結構的樹與二元樹（Trees and Binary Trees） - 林偉川老師
師大附中校隊 hackmd

紹宇的證明提供，我在證明這裡時突然卡關，我好笨RRRR

1
2
3
4
5
6
struct Node{
    int left; // 左邊邊界
    int right; //右邊邊界
    int value; //儲存的值
    int z; //區間修改用，如果沒有區間修改就不需要
}node[4 * N ];

透過實作來說明 Segment Tree 線段樹

這邊的問題則是給你一段數列，想請你告訴我們查詢的區間中最小值為何，下面的 question() 則是產生題目的數列。

建立線段樹

剛剛我們已經知道了節點數量的最大的大小，現在來進行建立的步驟。

我們要建立跟此網頁上第一張圖一樣的概念，直接透過程式碼說明，這邊我們要查詢的以最小值(min)為例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define Lson(x) (x << 1) //左子樹
#define Rson(x) ((x << 1) +1) //右子樹

void question(){
    for(int i = 1; i <= 10; i++) num[i] = i * 123 % 5; 
    // num 為題目產生的一段數列
    // hash 函數，讓 num 的 i 被隨機打亂
}

void build(int left , int right , int x = 1 ){ 
    // left 為題目最大左邊界，right 為題目最大右邊界，圖片最上面的 root 為第一個節點
    node[x].left = left ; //給 x 節點左右邊界
    node[x].right = right ;
    if(left == right){ //如果左右邊界節點相同，表示這裡是葉節點
        node[x].value = num[left] ;  //把 num 值給 node[x]
        //這裡的 num 值表示，我們要在 value 要放的值
        return ; //向前返回
    }
    int mid = (left + right ) / 2 ; //切半，產生二元樹

    //debug
    //cout << mid << '\n' ;
    //cout << x << ' ' << node[x].left << ' ' << node[x].right << ' ' << '\n' ;

    build(left , mid , Lson(x)) ; //將區間改為 [left, mid] 然後帶給左子樹
    build(mid + 1 , right , Rson(x)) ; //將區間改為 [mid+1, right] 然後帶給右子樹
    node[x].value = min(node[Lson(x)].value  , node[Rson(x)].value ) ;
    //查詢左右子樹哪個數值最小，並讓左右子樹最小值表示此區間最小數值。
}

單點修改

畢竟是線段樹，題目不可能數值都一成不變，有時候會進行變動，這裡我們將說明程式碼如何幫助線段樹進行單點修改。

基本上與建立相似，只是我們是先找到葉節點後，在向上比較，如果我們的值比較小就修改，沒有就保持原狀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void modify(int position , int value , int x = 1 ){ //修改數字
    if(node[x].left == position && node[x].right == position ){ //找到葉節點
       node[x].value = value ; //修改
       return ; //傳回
    }
    int mid = (node[x].left + node[x].right ) / 2 ; //切半，向下修改
    if(position <= mid ) //如果要修改的點在左邊，就往左下角追蹤
        modify(position , value , Lson(x) );
    if(mid < position ) //如果要修改的點在右邊，就往右下角追蹤
        modify(position , value , Rson(x)) ;
    node[x].value = min(node[Lson(x)].value , node[Rson(x)].value );
    //比較左右子樹哪個值比較小，較小值為此節點的 value

}

區間修改

線段樹中比較不好懂得部分，我們假設有一種題目是會把某個區間的值全加一個數字來進行舉例。

主要需要兩個 function 來寫

  • push_down，用來將先前的懶人標記往下推
  • update，用來將一開始的區間推至線段樹適合的位置

假如我們要在區間 \([1, 10]\)，都進行加二，線段數的目標是找區間最小值，這時我們需要呼叫 update，幫助我們找到線段樹節點 \([1, 10]\)，把這邊的數值加二，並且給予一個懶人標記表示下面的所有子樹都沒有被進行加二，因此懶人標記就會是加二；如果之後會查詢、區間修改到其他值時，我們就會利用 push_down 讓下一層的子樹執行區間加二的指令。

那如果都不需要再向下查詢，那就讓懶人標記一直維持在此不需要對下面子樹進行更動，降低時間複雜度。

但我很喜歡林品諺大佬的一句話，只在你需要的時候做事，有時候你不需要那麼勤勞。

我認為透過程式碼說明，勝過於簡單的文字說明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void push_down(int x, int add){ //將懶人標記往下推，讓下一層子樹進行區間修改
    int lson = Lson(x), rson = Rson(x);
    node[lson].z += add;  //給予懶人標記，表示子樹如果要給子樹的子樹區間修改時，
    node[rson].z += add;  //數值要是多少，左右子樹都需要做

    node[lson].v += add; //更新左右子樹的值
    node[rson].v += add;
}

void update(int a, int b, int cmd, int x = 1){ 
//a, b 為區間修改的 left and right, cmd 為要增加的數值 
    if(a <= node[x].l && b >= node[x].r){ 
        //如果節點的 left and right，跟 a, b 區間是相等，或更小就，只要在這邊修改 cmd，
        //就可以讓 node[x].v 的值直接變為區間修改後的數值，
        //之後如果要讓這查詢向子樹進行區間修改，就用 push_down，
        //我們這邊的懶人標記就會告訴左右子樹要修改的值為多少

        node[x].v += cmd; //區間修改後的 v
        node[x].z = cmd; //區間修改是要增加多少數值
        return; 
    }
    push_down(x);//先將之前的區間查詢修改值，往下給子樹以避免上次的查詢值被忽略
    //假如當前的 node[x].z 原本是 3，如果沒有 push_down(x)，那下面的子樹都沒有被 +3，
    //導致答案不正確。

    int mid = (node[x].l+node[x].r) / 2;  //切半，向下修改
    if(a <= mid) update(a, b, cmd, Lson(x)); //如果要修改的點在左邊，就往左下角追蹤
    if(b > mid) update(a, b, cmd, Rson(x)); //如果要修改的點在右邊，就往右下角追蹤
    node[x].v = node[Lson(x)].v + node[Rson(x)].v;
    //比較左右子樹哪個值比較小，較小值為此節點的 value
}

區間查詢

線段樹重要的部分，所有的線段樹一定會進行這個動作，但查詢的方式其實與二元樹相同，畢竟是透過二元樹建立的嘛XD。

我們將說明程式碼如何幫助線段樹進行區間查詢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define INF 0x3f3f3f

int query(int left , int right , int x = 1 ){
    if(node[x].left >= left && node[x].right <= right) 
        return node[x].Min_Value ;
    //如果我們要查詢的區間比當前節點的區間大，那我們不需再向下查詢直接輸出此答案就好。
    // 例如我們要查詢 [2, 8]，我們只需要查詢 [3, 4]，不須查詢 [3, 3]、[4, 4]，
    // [3, 4] 已經做到最小值查詢

    push_down(x);//有區間修改時才需要寫    
    int mid = (node[x].left + node[x].right ) / 2 ; //切半，向下修改
    int ans = INF ; //一開始先假設答案為最大值

    if( left <= mid ) //如果切半後，我們要查詢的區間有在左子樹就向下查詢
        ans = min(ans , query(left , right , Lson(x))) ; //更新答案，比較誰比較小
    if(mid < right ) //如果切半後，我們要查詢的區間有在右子樹就向下查詢
        ans = min(ans , query(left , right , Rson(x))) ; //更新答案，比較誰比較小
    return ans ; //回傳答案
}

不可離散化的 Segment Tree 線段樹

有時候會遇到一些題目的 n 可能大於 \(10^9\)，在 C++ 沒有辦法承擔那麼大的陣列大小時，我們可以用指標來解決這個問題，或是改使用 linklist 的方式，減少因為離散化而大量設定陣列值的問題。

參考連結

資料結構的樹與二元樹（Trees and Binary Trees） - 林偉川老師
師大附中校隊 hackmd
Segment/Interval Tree - 2 by 林品諺

紹宇的證明提供，我在證明這裡時突然卡關，我好笨RRRR

心得

好久沒有複習線段樹了，透過這此的編寫讓我把線段樹也重新複習了一遍，老實講我常常會覺得自己寫這些東西似乎沒用，畢竟我走資財，寫這些東西可能只能夠在純資的環境上使用，但我是資財的學生，我不知道自己到底用不用的到。

老實講，自己在高中學到的東西，非常快樂，非常充實。但在大學時感覺不到有一群跟我一樣愛好的人一起努力奮鬥，大家都有自己的目標要奮鬥，大家的目標不再只有那麼單一，都很多樣，有時候會讓我迷失方向，會讓我覺得我做這些事情有意義嗎。

Segment Tree 線段樹 無註解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#define INF 0x3f3f3f
#define Lson(x) (x << 1) 
#define Rson(x) ((x << 1) +1)
#define MAXN 題目陣列最大長度

struct Node{
    int left;
    int right; 
    int value; 
    int z; //不須區間修改就不用寫
}node[4 * N ]; 

void question(){
    for(int i = 1; i <= 10; i++) num[i] = i * 123 % 5; 
    // num 為題目產生的一段數列
    // hash 函數，讓 num 的 i 被隨機打亂
}

void build(int left , int right , int x = 1 ){ 
    node[x].left = left ;
    node[x].right = right ;
    if(left == right){ 
        node[x].value = num[left] ; 
        return ; 
    }
    int mid = (left + right ) / 2 ; 

    //debug
    //cout << mid << '\n' ;
    //cout << x << ' ' << node[x].left << ' ' << node[x].right << ' ' << '\n' ;

    build(left , mid , Lson(x)) ; 
    build(mid + 1 , right , Rson(x)) ;
    node[x].value = min(node[Lson(x)].value  , node[Rson(x)].value ) ;
}

void modify(int position , int value , int x = 1 ){
    if(node[x].left == position && node[x].right == position ){
       node[x].value = value ;
       return ;
    }
    int mid = (node[x].left + node[x].right ) / 2 ; 
    if(position <= mid ) 
        modify(position , value , Lson(x) );
    if(mid < position )
        modify(position , value , Rson(x)) ;
    node[x].value = min(node[Lson(x)].value , node[Rson(x)].value );

}

void push_down(int x, int add){ //將懶人標記往下推
    int lson = Lson(x), rson = Rson(x);
    node[lson].z = add;
    node[rson].z = add;

    node[lson].v += add;
    node[rson].v += add;
}

void update(int a, int b, int cmd, int x = 1){ 
    if(a <= node[x].l && b >= node[x].r){ 
        node[x].v += cmd;
        node[x].z = cmd;
        return;
    }
    push_down(x); 

    int mid = (node[x].l+node[x].r) / 2;
    if(a <= mid) update(a, b, cmd, Lson(x));
    if(b > mid) update(a, b, cmd, Rson(x));
    node[x].v = min(node[Lson(x)].v , node[Rson(x)].v);
}

int query(int left , int right , int x = 1 ){
    if(node[x].left >= left && node[x].right <= right) 
        return node[x].value ;
    push_down(x);//有區間修改時才需要寫
    
    int mid = (node[x].left + node[x].right ) / 2 ; 
    int ans = INF ;

    if( left <= mid ) 
        ans = min(ans , query(left , right , Lson(x))) ; 
    if(mid < right ) 
        ans = min(ans , query(left , right , Rson(x))) ; 
    return ans ;
}
  • 版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: