大小関係をCartesian treeへ変換する

概要

Cartesian treeによる区間極値分解

配列順と値のheap順を同時に保つ木を構成し、区間極値を根とする再帰分割へ変換する。

考え方

配列の添字をinorder、値をheap順に持つ木を作る。単調stackで右側の祖先鎖を更新すると、区間の最小値が対応する節点へ集まり、配列の分割を木構造として扱える。

stackから親子を確定する

最小値heapを作る場合、優先keyを(value,index)として同値でも全順序を定める。空stackから添字iを昇順に読み、keyがiより大きい末尾をpopし、最後にpopした頂点をlastとする。lastがあればiの左子をlast、親[last]=iとする。pop後の末尾pがあればpの右子をi、親[i]=pとする。その後iをpushする。stackは構築済み木の右端の祖先鎖であり、keyは増加する。

popした鎖はすべてiより大きく、最後のlastがその部分木の最小keyなのでiの左へ置ける。残ったpはiより小さいためiの親になる。添字順のinorderも保つ。最後のstackの先頭が根となり、空入力なら木は空。各頂点は一回push・popされるため線形構築である。区間[l,r]の最小keyの添字はlとrのLCAになり、各部分木のinorderが連続区間であることから区間の分割へ接続できる。

成立条件と計算量

構築O(N)。同値の優先を添字などで固定しないと木が一意にならない。LCAとRMQの対応には同じtie規則を使う。木の高さは最悪Nであり、平衡木と同じ深さを仮定しない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。単調stackから木を構築し、区間極値と再帰分割が同じ構造になることを使う。

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

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-cartesian-tree

習得する技能

  • 配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。

前提と範囲

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

直接の前提単元: 支配関係から不要な候補を単調stack・queueで削る。

このUnitを直接前提とする単元: なし。

単調stackの支配関係を親子関係へ持ち上げ、配列の区間極値を部分木境界として分割処理へ使う。

このUnitでは扱わないもの

  • 最近傍の大小関係だけを答える単調stack、および木を構成せず冪等演算へ答えるRMQ。

根拠