Euler順による部分木区間化
DFS入退時刻で各部分木を連続区間へ写し、配列上の更新・集約へ変換する。
この典型を扱う単元: Euler順による部分木区間化
検索別名: DFS order、Euler Tourによる部分木区間化、Euler tour flattening
未知問からこの典型を見つける手掛かり
- 扱う対象
- DFS順
- tin/tout
- 部分木
- 使う手掛かり
- subtree query
- 部分木更新
- 保つ不変量
- 入退時刻
- 連続区間
- 求めるもの
- 区間query
- 配列化
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
- 区間monoid要約: 部分木を連続区間へ写し、区間集約・一点更新・差分伝播へ接続するときに併用する。
学習成果と学習単位
Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。
Euler順による部分木区間化で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。