線段樹 (Segment Tree)

前言:

線段樹的功能很強大,可以支援各種區間操作

區間查詢(以RMQ為例):

  • 相對ST表而言,這分法犧牲了查詢複雜度,但仍舊可以解決大部分區間查詢的問題
  • 線段樹的常數有點大,請多多留意~

方法:

  • 考慮把區間拆成
    O(logn)
    個「不重疊的」區間
  • 建表建成這樣(對於以下這些區間建立最大值):
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 這麼一來,
    • 建表複雜度:
      O(n)
    • 查詢複雜度:
      O(logn)

單點修改:

  • 如果只有單點修改,很簡單
  • 觀察一下上面的圖,如果我們要將點k做修改,會發現整棵樹包含到點k的區間只有
    O(logn)
    個,所以:
    • 時間複雜度:
      O(logn)

區間修改(以 RMQ 為例):

  • 如果修改一個區間,最暴力的作法是把每個區間內的點做單點修改。
    • 時間複雜度:
      O(n)
  • 似乎有點太大!
  • 沒關係,現在才是線段樹真正厲害的地方~~!
  • 我們從區間查詢的方法,發現如果我們只修改至多這
    O(logn)
    個區間就好了~
    • 時間複雜度:
      O(logn)
  • 可是有些需要被修改的點就沒被改到阿!?沒關係,我們有懶人標記。

懶人標記(lazy tag)

  • 如果我們修改了一個點,並且那個點之後都沒被查詢,那不修改也沒差對吧(?)
  • 所以我們只要記得這個區間有被修改過,並且查詢時,分別告訴左右子樹(如果有的話),你們也被修改了!
  • 講的抽象,舉個例子:
    • 你現在是小主管,總經理要發年終獎金給大家,並且拿一部分給你的老闆(Alien),希望你的老闆(Bob)分配給你底下的成員。
    • 有趣的事情來了:
    1. 你的老闆(Bob)懶得發下去,就先自己獨吞了>_<
    2. 總經理(Alien)也不是笨蛋,他要去檢查你有沒有拿到年終獎金。
    3. 你的老闆(Bob)不得已,只好把獎金發給你們了
    4. 於是你通過檢查了~
    5. 這次換你懶得發下去,就先自己獨吞了>_<
    6. 總經理(Alien)也不是笨蛋,他要去檢查你的下屬(Clinton)有沒有拿到年終獎金。
    7. 你被迫將該給你下屬們的年終獎金發給它們
    8. 於是你的下屬(Clinton)通過檢查了~