Bo2SS

[學習數據結構主要關注解決的是什麼問題]

課程內容#

前置知識#

• 解決的問題是什麼？區間的修改與查詢 [針對積性函數——Wiki]
• 問題背景
  • 
  • 單點修改、區間查詢（基礎版）
    • Modify (ind, val)：修改 ind 位置的值為 val
    • Query (start, end)：查詢 start~end 位置值的和
  • 區間修改、區間查詢（進階版）
  • 單點修改、單點查詢（用不著線段樹，數組即可）
  • 區間修改、單點查詢（其實就是進階版的特例）

基礎版線段樹#

• 區間組成的樹→區間的和值組成的樹 [線段樹]
  • 
  • 👇
  • 
  • 【構建過程】採用的分治的思想，將總區間分成左右兩部分，一直進行下去，直到區間中只剩下一個結點為止
  • 【要維護的性質】結點統計的是一個區間的和值
    • 葉子結點代表了原序列中的單個位置的值
  • [PS] 回顧：樹的結點代表集合，邊代表關係
• 單點修改
  • 遞歸，找到要修改的結點，修改，然後
  • 回溯，修改路徑上每一個祖先結點的統計和值 [根結點到葉結點的路徑]
• 區間查詢
  • 一個點可能代表一個區間的和值，查詢更快
    • 如果直接使用數組，則需要一個一個查值
    • 如果借助前綴和數組，則單點修改非常耗時
• ⭐線段樹，其實是用來維護一維序列的高級數據結構
  • 時間複雜度 [與樹高有關]
    • 單點修改：O (logN)
    • 區間查詢：O (logN)
    • N 代表一維序列的長度
• ❓ 問題思考
  • 若採用完全二叉樹的存儲方式，N 個點的線段樹最多需要多少個結點空間？【4N】
    • 先考慮用普通二叉樹 [線段樹一定是滿二叉樹] 存儲，參考上圖
    • 葉子結點數為 N，則度為 2 的結點數為 N - 1 [二叉樹的性質：度為 0 的結點比度為 2 的結點多 1 個]，所以結點數為 2N - 1
    • 而如果用完全二叉樹的存儲方式，則最多還要預留 2 倍葉子結點數的結點空間 2N [完全二叉樹的性質：兩個子結點的索引與父結點 i 之間的關係是 2i 和 2i + 1 ]
    • 所以最多需要 4N 個結點空間
  • 如何做區間修改？ [大小為 m 的區間上每一個值都做修改]
    • 基於線段樹的基本操作：O (m * logN)，相當於脫了褲子放屁
    • 而直接在原有區間上修改：O (m)，本身就比用線段樹好
    • 請看進階版：O (logN)
• [PS] 只適用於單點修改、區間查詢 【基礎版】
  • 當面對區間修改的時候，基礎版的線段樹效率上還不如直接在一維序列上修改

進階版線段樹#

區間修改 [⭐]#

• Modify 操作
  • 
  • ⭐懶標記：不對其子結點立即發數值，碰到結點查詢 [修改操作/ 查詢操作遍歷時] 時才下發
  • 類比 [懶政]：皇帝 [根結點] 給百姓 [葉子結點] 下發糧食，先發給上級 [子結點]，上級會先收著，等到皇帝親自視察時才往下分發糧食
• Query 操作
  • 
  • 觸發懶標記下發數值
• 時間複雜度 [同區間查詢操作]：O (logN)

關鍵詞#

• 完全二叉樹 [存儲結構]
• 區間 [每個結點的維護範圍]
• 向上更新 [回溯過程]
• 下沉標記 [懶標記]
• ⭐口诀⭐ 下沉發生在遞歸之前，向上發生在遞歸之後
  • 標記下沉發生在遞歸之前，向上更新發生在具有修改操作的遞歸之後

隨堂練習#

HZOJ-222：線段樹模板 (一)#

範例輸入

6 5
6 9 4 3 2 1
2 2 5
1 2 3
2 1 6
1 5 12
2 1 6

範例輸出

9
6
12

• 思路
  • 父結點所在區間的最大值可以由子結點得到
  • 【線段樹應用場景】父結點的相關信息可以由子結點得到
• 代碼
• ① 易理解版 [有 l、r]
  • 
  • 
  • 
  • 使用 scanf/printf 讀入數據或者關閉同步流，否則會超時
  • 查詢最大值操作，在縮小查詢範圍時始終保持修改查詢區間邊界，否則會有擴大查詢區間的可能
• ② 優化版 [無 l、r]
  • 
  • 
  • 
  • 可做空間的優化：結點不存儲 l、r 信息
    • 不影響建樹過程
    • ⭐修改和查詢操作額外添加【當前結點所維護的區間範圍】

HZOJ-223：線段樹模板 (二)#

範例輸入

6 5
6 9 4 3 2 1
2 2 5
1 2 3 5
2 1 6
1 5 12 3
2 1 6

範例輸出

18
35
41

• 思路
  • 加入懶標記
  • 注意輸出的提示：答案在 long long 範圍內
• 代碼
  • 
  • 
  • 
  • 一定要區分好【結點維護的區間範圍 l ~ r】，以及【查詢的區間 x ~ y】
  • [PS] 學會利用 flag 起到註釋調試代碼的效果；數據範圍為 long long
  • ⭐⭐⭐只要遍歷就需要下沉，即使是區間修改時
    • 如果區間修改中遍歷結點時【不下沉標記】，向上更新可能引發問題
    • 可以嘗試測試兩種方式下，下面輸入的輸出
      • ❗ 連續兩次區間修改，第二次修改層數更深，向上更新時會少考慮懶標記，因為向上更新和值的操作只會看子樹的和值，默認自己沒有懶標記了
      • 遍歷時就下沉標記實現更簡單，也更易理解

5 5
1 2 3 4 5
1 1 3 2
1 1 2 2
2 1 3

• 結果如下：
  • 
  • modify (1, 3, 2) : 1, 1, 5, 15，代表給 [1, 3] 區間 + 2，此時在 1 號結點 [根結點]，維護區間為 [1, 5]，sum 為 15
  • 自行畫樹形圖可加深理解

思考點#

• 好好琢磨下沉標記和向上更新的過程！

Tips#

• 關注口诀，船長歸納得很妙！
• 更多習題可跳轉：《面試筆試算法下》——6 樹狀數組、線段樹練習題