4 セグメントツリー

[データ構造を学ぶ主な焦点は何の問題を解決するか]

コース内容#

前提知識#

解決する問題は何ですか？区間の変更とクエリ [対象積性関数——Wiki]
問題の背景
- 単点変更、区間クエリ（基本版）
  - Modify (ind, val)：ind 位置の値を val に変更
  - Query (start, end)：start~end 位置の値の合計をクエリ
- 区間変更、区間クエリ（進階版）
- 単点変更、単点クエリ（セグメントツリーは不要、配列で十分）
- 区間変更、単点クエリ（実際には進階版の特例）

基本版セグメントツリー#

区間で構成された木→区間の合計で構成された木 [セグメントツリー]
- 👇
- 【構築プロセス】分治法を用いて、全区間を左右の 2 つの部分に分け、区間に 1 つのノードが残るまで続ける
- 【維持すべき性質】ノードは 1 つの区間の合計をカウント
  - 葉ノードは元の配列の単一位置の値を表す
- [PS] 振り返り：木のノードは集合を表し、辺は関係を表す
単点変更
- 再帰的に、変更するノードを見つけて変更し、その後
- 戻り、変更経路上の各祖先ノードの合計を更新 [根ノードから葉ノードへの経路]
区間クエリ
- 1 つの点が区間の合計を表す可能性があり、クエリが速い
  - 配列を直接使用する場合、1 つずつ値をクエリする必要がある
  - プレフィックス和配列を利用する場合、単点変更は非常に時間がかかる
⭐セグメントツリーは、実際には 1 次元配列を維持するための高度なデータ構造
- 時間計算量 [木の高さに依存]
  - 単点変更：O (logN)
  - 区間クエリ：O (logN)
  - N は 1 次元配列の長さを表す
❓ 問題の考察
- 完全二分木のストレージ方式を採用した場合、N 個の点のセグメントツリーは最大で何個のノードスペースが必要ですか？【4N】
  - まず通常の二分木 [セグメントツリーは必ず完全二分木] でのストレージを考慮し、上の図を参照
  - 葉ノード数は N で、度が 2 のノード数は N - 1 [二分木の性質：度が 0 のノードは度が 2 のノードより 1 つ多い] なので、ノード数は 2N - 1
  - 完全二分木のストレージ方式を使用する場合、最大で葉ノード数の 2 倍のノードスペースを予約する必要がある 2N [完全二分木の性質：2 つの子ノードのインデックスと親ノード i の間の関係は 2i と 2i + 1]
  - したがって、最大で 4N のノードスペースが必要
- 区間変更はどう行いますか？ [サイズ m の区間のすべての値を変更]
  - セグメントツリーの基本操作に基づく：O (m * logN)、つまり無駄な操作
  - 元の区間で直接変更する場合：O (m)、そもそもセグメントツリーを使用するよりも良い
  - 進階版を見てください：O (logN)
[PS] 単点変更、区間クエリにのみ適用されます【基本版】
- 区間変更に直面した場合、基本版のセグメントツリーは 1 次元配列での変更よりも効率が悪い

進階版セグメントツリー#

区間変更 [⭐]#

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] フラグを利用してコードのデバッグ効果を得ることを学ぶ；データ範囲は long long
- ⭐⭐⭐遍歴する場合は常に遅延を下げる必要があり、区間変更時も同様
  - 区間変更中にノードを遍歴する際に【遅延マークを下げない】と、上向き更新が問題を引き起こす可能性がある
  - 次の入力の出力を 2 つの方法でテストしてみることができる
    - ❗ 連続して 2 回区間変更を行うと、2 回目の変更の層が深くなり、上向き更新時に遅延マークを考慮しない可能性がある
    - 遍歴時に遅延マークを下げることで、実装が簡単で理解しやすくなる