コンテンツにスキップ

Cartesian Tree のリンク集

Cartesian Tree について、参考になる記事や資料をまとめました。

Cartesian Tree は、数列の最小値を根にし、その左側と右側の部分列から左右の部分木を再帰的に作った二分木です(最大値を根にする流儀もあります)。添字について見ると二分探索木、値について見るとヒープになっています。スタックを使えば O(N)O(N) で構築できます。「区間を最小値で分割して再帰する」分割統治は、この木の上の再帰とみなせます。

同じ値があるときは、どちらを小さいとみなすかで木の形が変わります。下の資料の多くは左端の最小値を根にしていますが、右端を根にするものもあるので注意してください。

区間最小値(RMQ)は、Cartesian Tree の上の 2 頂点の最小共通祖先(LCA)に対応します。

  • 前処理O(n)クエリO(1)のLCAと静的RMQ(joisino)
    • RMQ を Cartesian Tree の上の LCA に帰着させ、前処理 O(n)O(n)・クエリ O(1)O(1) を実現する記事です。スタックによる構築も図で説明しています。
  • Solve RMQ by finding LCA(cp-algorithms、英語)
    • RMQ が LCA に帰着できることの説明と、スタックによる構築のコードがあります。このコードでは、同じ値があると右端の最小値が根になります。
  • LCA and RMQ 簡潔もあるよ!(井上祐馬、スライド)
    • RMQ から LCA への帰着から、簡潔データ構造まで扱う上級者向けの資料です。

Cartesian Tree を扱う講座はまだありません。

  • Cartesian Tree(Nyaan’s Library)
    • 日本語のドキュメントつきの実装です。同じ値があるときは左端の最小値を根にすると明記されています。戻り値は子のリストと根の組で、左右の子は区別されません。

百科事典・英語・中国語の資料

Section titled “百科事典・英語・中国語の資料”
  • Cartesian tree(英語版 Wikipedia)
    • 定義と同じ値の扱い、線形時間の構築法をいくつか、RMQ・LCA や Treap との関係までを網羅しています。日本語版の記事はありません。
  • 笛卡尔树(OI Wiki、中国語)
    • 右端の鎖を単調スタックで管理する O(n)O(n) 構築を図とコードで説明し、ヒストグラム中の最大長方形への応用を例題として扱っています。
  • Treap (Cartesian tree)(cp-algorithms、英語)
    • ロシア語圏などでは Treap のことも Cartesian tree と呼ぶため、この記事の題に入っています。中身は Treap の解説で、数列から作る Cartesian Tree の説明ではありません。