「 學習筆記 」線段樹合併
線段樹合併
普通線段樹 \((\) 無懶惰標記 \()\)
時間複雜度 & 空間複雜度
假設有 \(2\) 棵線段樹，它們的結點個數之和為 \(s\)，那麼建樹 時間複雜度 是 \(O(s)\) 的。
為了簡單表達，第 \(i\) 棵線段樹用 \(\{ i \}\) 表示。
考慮 ${ x } $ 和 \(\{ y \}\) 的合併：\((\) 以下的結點指表示區間相同的結點，例如根結點都表示 \(\mathrm{down} \sim \mathrm{up}\) \()\)
- 情況 \(1\) \(\{ x \}\) 和 \(\{ y \}\) 都存在的結點：
- 這 \(2\) 個結點合併可以視作給其中 \(1\) 個結點 \(+1\)；
- 因此 時間複雜度 為 \(+1\) 的次數；在這個情況下，每個結點至多執行 \(1\) 次 \(+1\) 操作，至多有 \(s\) 個結點，所以 時間複雜度 的上屆是 \(O(1 \times s) = O(s)\)。
- 情況 \(2\) \(\{ x \}\) 和 \(\{ y \}\) 中至少有一個不存在的結點：
- 此時它們的父親結點一定都是存在的，不然就不會遞歸到這裡了，同時也不需要往下遞歸了，對 時間複雜度 的貢獻可以視作給父親結點 \(+1\)；
- 在這個情況下，一個父親結點至多執行 \(2\) 次 \(+1\) 操作，至多有 \(s\) 個父親結點，所以 時間複雜度 的上屆是 \(O(2 \times s) = O(2s)\)。
綜上所述：\(2\) 棵線段樹合併的時間複雜度為 \(O(s)\)。
這個結點可以推廣到多棵線段樹合併：記它們的結點個數之和為 \(S\)，那麼線段樹合併的時間複雜度為 \(O(S)\)，空間複雜度也為 \(O(S)\)。
