4 セグメントツリー

[データ構造の学習は主に何の問題を解決するか]

コース内容#

前提知識#

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

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

区間から構成される木→区間の合計から構成される木 [セグメントツリー]
- 👇
- 【構築プロセス】分治法を用いて、全区間を左右の部分に分け、区間にノードが 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 回目の変更の深さが深くなり、上向き更新時に遅延フラグを考慮しない可能性がある、なぜなら上向き更新と合計の操作は子木の合計のみを見て、デフォルトでは自分に遅延フラグがないと仮定するから
    - 遍歴時に遅延フラグを下すことは、より簡単で理解しやすい