Cartesian Tree のリンク集
Cartesian Tree について、参考になる記事や資料をまとめました。
Cartesian Tree は、数列の最小値を根にし、その左側と右側の部分列から左右の部分木を再帰的に作った二分木です(最大値を根にする流儀もあります)。添字について見ると二分探索木、値について見るとヒープになっています。スタックを使えば で構築できます。「区間を最小値で分割して再帰する」分割統治は、この木の上の再帰とみなせます。
同じ値があるときは、どちらを小さいとみなすかで木の形が変わります。下の資料の多くは左端の最小値を根にしていますが、右端を根にするものもあるので注意してください。
まず読むもの
Section titled “まず読むもの”- Cartesian Tree の実装 〜 stack を用いた O(N) 時間構築(けんちょんの競プロ精進記録)
- 定義から始めて、スタックで で構築する手順を、具体例でのスタックの推移表と C++ 実装つきで解説しています。使える問題へのリンクもあります。
- 列を最小値で分割して再帰するパターンと Cartesian tree(うさぎ小屋)
- 最小値で列を分割して再帰する分割統治が Cartesian Tree の上の再帰そのものだと整理し、例題 3 問で使い方を示しています。Treap との用語の違いにも触れています。
RMQ・LCA との関係
Section titled “RMQ・LCA との関係”区間最小値(RMQ)は、Cartesian Tree の上の 2 頂点の最小共通祖先(LCA)に対応します。
- 前処理O(n)クエリO(1)のLCAと静的RMQ(joisino)
- RMQ を Cartesian Tree の上の LCA に帰着させ、前処理 ・クエリ を実現する記事です。スタックによる構築も図で説明しています。
- Solve RMQ by finding LCA(cp-algorithms、英語)
- RMQ が LCA に帰着できることの説明と、スタックによる構築のコードがあります。このコードでは、同じ値があると右端の最小値が根になります。
- LCA and RMQ
簡潔もあるよ!(井上祐馬、スライド)- RMQ から LCA への帰着から、簡潔データ構造まで扱う上級者向けの資料です。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”Cartesian Tree を扱う講座はまだありません。
- Cartesian Tree(Nyaan’s Library)
- 日本語のドキュメントつきの実装です。同じ値があるときは左端の最小値を根にすると明記されています。戻り値は子のリストと根の組で、左右の子は区別されません。
百科事典・英語・中国語の資料
Section titled “百科事典・英語・中国語の資料”- Cartesian tree(英語版 Wikipedia)
- 定義と同じ値の扱い、線形時間の構築法をいくつか、RMQ・LCA や Treap との関係までを網羅しています。日本語版の記事はありません。
- 笛卡尔树(OI Wiki、中国語)
- 右端の鎖を単調スタックで管理する 構築を図とコードで説明し、ヒストグラム中の最大長方形への応用を例題として扱っています。
- Treap (Cartesian tree)(cp-algorithms、英語)
- ロシア語圏などでは Treap のことも Cartesian tree と呼ぶため、この記事の題に入っています。中身は Treap の解説で、数列から作る Cartesian Tree の説明ではありません。
- Library Checker - Cartesian Tree:構築するだけの問題で、値はすべて異なります。
- ABC435 F - Cat exercise:最大値を根にする Cartesian Tree の上で木 DP をします(公式解説)。
- ARC189 D - Takahashi is Slime:公式解説の本筋はセグメント木上の二分探索ですが、Cartesian Tree を使って解く方法にも触れています(公式解説)。
- ARC212 E - Drop Min:Cartesian Tree の上で数え上げの木 DP をします(公式解説)。
- ARC115 E - LEQ and NEQ:DP の遷移を Cartesian Tree の構造に注目してまとめます(公式解説)。
- TTPC2024 (Div.1) M - Cartesian Trees:区間から作る Cartesian Tree の形の種類を数える難問です(解説)。
このブログの記事
Section titled “このブログの記事”- SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain
- 復元できる数列と Cartesian Tree の形の対応を使って数え上げています。同じ値は後ろにあるほうを小さいとみなすので、右端の最小値が根になります。