Day 154-Q2 — Cartesian Tree（デカルト木）

2026-09-15 赤色 Master / Phase 8+ ★★★★★★★★★ 配列のインデックス順=中間順序、値=最小ヒープ順序を同時に満たす二分木をO(N)構築

問題

長さ $N$ の相異なる整数からなる数列 $a_1, a_2, \dots, a_N$ が与えられる。この数列から デカルト木（Cartesian Tree） を構築せよ。デカルト木とは以下を満たす二分木である。

  • 中間順序（in-order）で頂点を並べると、配列のインデックス順 $1,2,\dots,N$ に一致する
  • 各頂点の値は、その部分木内のすべての頂点の値の中で最小である（最小ヒープ順序）

各インデックス $i$ について、頂点 $i$ の親のインデックスを出力せよ。根の親は $0$ とする。

入力形式

N
a_1 a_2 ... a_N

制約

$1 \le N \le 2 \times 10^5$
$a_i$ は相異なる整数, $1 \le a_i \le 10^9$

入出力例

入力例1

7
5 3 8 1 9 2 7

出力例1

2 4 2 0 6 4 6

概念図：構築されたデカルト木（中間順序=配列順）

根=全体最小値(idx4,val1) 中間順序=1,2,3,4,5,6,7 idx4 val1 idx2 val3 idx6 val2 idx1 val5 idx3 val8 idx5 val9 idx7 val7 配列: idx 1..7 → val 5,3,8,1,9,2,7 出力parent: 2 4 2 0 6 4 6

ヒント（段階的開示）

ヒント1（方向性）

すべてのペア $(i,j)$ について親子関係を総当たりで決めると $O(N^2)$ かかる。分割統治で「区間の最小値を根にして左右に再帰」でも最悪 $O(N^2)$（ソート済み配列で発生）になる。$O(N)$ にするには、配列を左から1回だけ走査する方法を考える。

ヒント2（アプローチ）

値が増加する列を保つスタックを使う。新しい要素 $a_i$ を見るとき、スタックの上から $a_i$ より大きい値を持つ要素を全部ポップする。最後にポップされた要素（あれば）は $a_i$ の左の子になる。ポップ後に残っているスタック最上位（あれば）は $a_i$ の親になる。各要素が高々1回push・1回popされるだけなので全体 $O(N)$。

ヒント3（誘導） 
parent = [0] * (N + 1)
stack = []  # 増加列を保つスタック（インデックスを積む）
for i in range(1, N + 1):
    last = 0
    while stack and a[stack[-1]] > a[i]:
        last = stack.pop()
    if stack:
        parent[i] = stack[-1]   # 右の子として繋がる
    if last:
        parent[last] = i        # 左の子として繋がる（i が last の親になる）
    stack.append(i)

模範解答 (Python)

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    a = [0] + list(map(int, input().split()))

    parent = [0] * (N + 1)
    stack = []

    for i in range(1, N + 1):
        last = 0
        while stack and a[stack[-1]] > a[i]:
            last = stack.pop()
        if stack:
            parent[i] = stack[-1]
        if last:
            parent[last] = i
        stack.append(i)

    print(*parent[1:])


main()

Step-by-Step 解説

1$i=1, a_1=5$
スタック空なのでそのままpush。stack=[1]。
2$i=2, a_2=3$
$a[1]=5>3$ でポップ（last=1）。スタック空になったので親は設定せず。parent[1]=2（頂点1が頂点2の左の子）。push。stack=[2]。
3$i=3,4$（$a_3=8, a_4=1$）
$a_3=8$: ポップなし、parent[3]=2（右の子・暫定）、stack=[2,3]。$a_4=1$: $a[3]=8>1$, $a[2]=3>1$ を連続ポップ（last=2）、スタック空、parent[2]=4（頂点2が頂点4の左の子）、stack=[4]。
4$i=5,6,7$ と最終確認
同様の操作で parent=[_,2,4,2,0,6,4,6] が得られ、出力 2 4 2 0 6 4 6 と一致。根は parent[4]=0（値1=全体最小値）で最小ヒープ順序の条件と一致し、中間順序を辿ると 1,2,3,4,5,6,7 の順（インデックス順）になることも確認できる。

よくあるミス

ミス原因正しい書き方
lastの更新を「最初にポップした要素」にしてしまう「左の子は直前の1個だけ」という誤解lastはループ内で毎回上書きし、最後にポップされた要素を左の子にする
スタック更新の代入順序を間違えるright-child/left-child代入の混乱ポップ→parent[i]=stack[-1]→parent[last]=i→pushの順を厳守する
重複値がある入力にそのまま使うa[stack[-1]]>a[i]の等号なし比較は重複値で挙動不定重複を許す場合は同値時のタイブレーク（インデックス比較等）を追加する
根の判定を「parent配列に0が複数ある」と誤解バグ時の複数根に気づかない正しい実装では根はちょうど1つ。parent.count(0)==1で検証する
スタックに値そのものを積むインデックスと値の混同スタックにはインデックスを積み、値は都度a[stack[-1]]で参照する

次のステップ

  • 発展: デカルト木は配列上のRMQと木上のLCAが等価であることの証明に使われる（$\pm1$ RMQ への帰着）。構築した木上でLCAを求め、対応区間の最小値と一致するか確認せよ。
  • 次回予告: 永続Binary Trie（Persistent XOR Trie）

自己評価

自分の回答

気づき・メモ