Segment Treeのcanonical区間分解
区間をO(log N)個のcanonical nodeへ分解してrange object・生存時間・range edgeを配置し、point queryでは対応するroot-to-leaf pathから該当objectを集める。
この典型を扱う単元: Segment Treeのcanonical区間分解
検索別名: Segment Tree canonical cover、canonical区間分解、segment tree graph、時間セグメント木
未知問からこの典型を見つける手掛かり
- 扱う対象
- canonical node
- 区間
- 時間軸
- 使う手掛かり
- range edge
- 区間へ登録
- 生存区間
- 保つ不変量
- O\(log N\) nodes
- 完全被覆
- 求めるもの
- offline dynamic
- 区間object配置
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。
Segment Treeのcanonical区間分解で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC342 G「Retroactive Range Chmax」 公式問題主題: Segment Treeのcanonical区間分解 / 主タグ
技能・出典
主題: Segment Treeのcanonical区間分解
主タグ: Segment Treeのcanonical区間分解 / 補助タグ: ordered set・multisetの動的順序管理
- ABC414 G「AtCoder Express 4」 公式問題主題: 最短路モデル / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC244 Ex「Linear Maximization」 公式問題主題: 凸包・支持方向・境界候補 / 補助タグ
- ABC342 G「Retroactive Range Chmax」 公式問題主題: Segment Treeのcanonical区間分解 / 主タグ
技能・出典
主題: Segment Treeのcanonical区間分解
主タグ: Segment Treeのcanonical区間分解 / 補助タグ: ordered set・multisetの動的順序管理
- ABC363 G「Dynamic Scheduling」 公式問題主題: rollback・DFS入退場の状態復元 / 補助タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解
- ABC414 G「AtCoder Express 4」 公式問題主題: 最短路モデル / 補助タグ