Segment Treeのcanonical区間分解

概要

区間をO(log N)個のcanonical nodeへ分解してrange object・生存時間・range edgeを配置し、point queryでは対応するroot-to-leaf pathから該当objectを集める。

考え方

区間をSegment Treeの互いに素な最大節点区間へ分ける。O(log N)個の節点を使うことで、区間を対象とする制約や辺を個別要素すべてへ作らず表現できる。

node区間とquery[L,R)が交わらなければ停止、完全に含まれればそのnodeへ対象を置いて停止、部分交差なら両子へ進む。各深さで部分交差するnodeは左端・右端の高々二つで、その脇の完全被覆nodeだけを選ぶため全選択数はO(log N)。選ばれるnode区間は互いに素で、合併はちょうど[L,R)となる。

位置pを含む対象を集めるにはleaf pからrootへのpathの配置物を見る。pが対象区間に含まれる必要十分条件は、そのcanonical分解の一nodeがこのpath上にあることで、同じ対象が一queryで重複しない。range edgeでは外部頂点→区間の各点に届かせるdown tree(親→子)、区間の各点→外部頂点にはup tree(子→親)を分け、canonical nodeへ元辺重みで接続する。共有leaf以外で両向き木を無条件に結ぶと許さない移動を作るため、補助辺の向きを固定する。

成立条件と計算量

Q区間の分解数はO(Q log N)。区間graphへの帰着では上向き・下向きの補助辺を分ける。query合成と補助graph構築は用途が違うため、最終graphの頂点・辺数と探索費用も数える。

下位単元

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。区間を少数のnodeへ分解する性質を、値の集約以外の配置にも使う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 結合的な区間要約・区間分解・合成。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-segment-tree-canonical-decomposition

Segment Treeのcanonical区間分解

習得する技能

  • 区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 区間monoid要約。

このUnitを直接前提とする単元: 静的sorted range index・Merge Sort Tree。

区間monoid要約で得た考え方と実装を再利用し、Segment Treeのcanonical区間分解の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • Segment Treeのcanonical区間分解の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠