Day 104-Q1 | 永続セグメント木（Persistent Segment Tree）

問題

長さ $N$ の数列 $A=(A_1,\dots,A_N)$ が与えられる。$Q$個のクエリ $(l_i, r_i, k_i)$ が与えられ、各クエリについて「区間 $[l_i,r_i]$（1-indexed、両端含む）を昇順に並べたとき $k_i$ 番目に小さい値」を答えよ。同じ値は重複してカウントする。

接頭辞ごとの「値の出現回数」を持つセグメント木を作ると、接頭辞が1つ伸びるたびに変化するノードは $O(\log(\max A))$ 個だけであり、残りは前のバージョンと共有できる。この「変化しない部分は使い回し、変化する部分だけ新しく作る」データ構造を 永続セグメント木 と呼ぶ。2つのバージョンの対応ノードのカウントを引き算しながら木を降りることで、任意区間の分布を復元できる。

入力形式

N
A_1 A_2 ... A_N
Q
l_1 r_1 k_1
...
l_Q r_Q k_Q

制約

$1 \le N,Q \le 2\times10^5$

$0 \le A_i \le 10^9$

$1 \le l_i \le r_i \le N$

$1 \le k_i \le r_i-l_i+1$

入出力例

入力例1

出力例1

1
1

区間$[1,5]=\{3,1,4,1,5\}$を昇順にすると$\{1,1,3,4,5\}$、1番目は1。区間$[2,4]=\{1,4,1\}$を昇順にすると$\{1,1,4\}$、2番目も1。

概念図: バージョン間のノード共有

ヒント（段階的開示）

ヒント1: 方向性

クエリごとに区間をソートするのは $O((r-l)\log(r-l))$ かかり間に合わない。区間$[l,r]$のヒストグラムをクエリごとに一から作るのも重い。「接頭辞のヒストグラムを何度も使い回せないか」を考えよう。

ヒント2: アプローチ

接頭辞$i$ごとの値の出現回数を持つセグ木を全て持ちたいが、毎回ゼロから作ると重い。接頭辞$i-1$から$i$への変化は「$A_i$のランクに対応する葉から根までのパス」だけなので、その差分ノードだけ新規作成し、残りは前バージョンのノードを使い回す（永続化）。クエリはバージョン$r$と$l-1$の対応ノードのカウント差を見ながら二分探索する。

ヒント3: 誘導（コード骨格）

def update(prev, lo, hi, pos):
    if lo == hi:
        return 新ノード(cnt=cnt[prev] + 1)
    mid = (lo + hi) // 2
    if pos <= mid:
        left = update(左の子[prev], lo, mid, pos)
        right = 右の子[prev]        # 使い回す
    else:
        left = 左の子[prev]          # 使い回す
        right = update(右の子[prev], mid + 1, hi, pos)
    return 新ノード(left, right, cnt[left]+cnt[right])

def query(u, v, lo, hi, k):   # u=roots[l-1], v=roots[r]
    if lo == hi: return lo
    mid = (lo + hi) // 2
    left_cnt = cnt[左の子[v]] - cnt[左の子[u]]
    if k <= left_cnt:
        return query(左の子[u], 左の子[v], lo, mid, k)
    return query(右の子[u], 右の子[v], mid+1, hi, k - left_cnt)

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    a = list(map(int, data[idx:idx + n])); idx += n
    q = int(data[idx]); idx += 1
    queries = []
    for _ in range(q):
        l = int(data[idx]); r = int(data[idx + 1]); k = int(data[idx + 2])
        idx += 3
        queries.append((l, r, k))

    sys.setrecursionlimit(500000)

    sorted_vals = sorted(set(a))
    comp = {v: i for i, v in enumerate(sorted_vals)}
    m = len(sorted_vals)

    seg_l = [0]
    seg_r = [0]
    seg_cnt = [0]

    def new_node(l, r, cnt):
        seg_l.append(l)
        seg_r.append(r)
        seg_cnt.append(cnt)
        return len(seg_cnt) - 1

    def update(prev, lo, hi, pos):
        if lo == hi:
            return new_node(0, 0, seg_cnt[prev] + 1)
        mid = (lo + hi) // 2
        if pos <= mid:
            left = update(seg_l[prev], lo, mid, pos)
            right = seg_r[prev]
        else:
            left = seg_l[prev]
            right = update(seg_r[prev], mid + 1, hi, pos)
        return new_node(left, right, seg_cnt[left] + seg_cnt[right])

    roots = [0]
    for v in a:
        roots.append(update(roots[-1], 0, m - 1, comp[v]))

    def query(u, v, lo, hi, k):
        if lo == hi:
            return lo
        mid = (lo + hi) // 2
        left_cnt = seg_cnt[seg_l[v]] - seg_cnt[seg_l[u]]
        if k <= left_cnt:
            return query(seg_l[u], seg_l[v], lo, mid, k)
        else:
            return query(seg_r[u], seg_r[v], mid + 1, hi, k - left_cnt)

    out = []
    for l, r, k in queries:
        pos = query(roots[l - 1], roots[r], 0, m - 1, k)
        out.append(str(sorted_vals[pos]))
    print('\n'.join(out))


solve()

計算量: $O((N+Q)\log(\max A))$（座標圧縮 + 永続セグ木の構築・クエリ）。stress test（ランダム200ケース）で愚直解と一致することを確認済み。

Step-by-Step 解説

1座標圧縮
$A_i\le10^9$なので、値の集合を昇順ソートしランク付けし、圧縮後の空間$[0,m)$でセグ木を構築する。

2各接頭辞バージョンの構築
`roots[i]`は`roots[i-1]`に対して「$A_i$のランクに$+1$する更新」を永続的に適用した結果。更新パス上だけ新規ノードを作り、他は使い回す。

3区間クエリを差分で処理
区間$[l,r]$のヒストグラムは「`roots[r]` − `roots[l-1]`」。2つの木を同時に根から辿り、各ノードで左の子のカウント差を計算する。

4二分探索でk番目を特定
左半分の個数が$k$以上なら左へ、そうでなければ$k$から引いて右へ。葉に到達した位置が答えのランク。

よくあるミス

ミス	原因	正しい書き方
座標圧縮を忘れ生の値をそのまま添字にする	値域$10^9$でメモリ超過	`sorted(set(a))`でランク付けし圧縮空間で構築
更新時に既存ノードを直接書き換える	過去バージョンまで壊れ永続性が失われる	更新パス上は必ず新規ノードを作り、変化しない子は使い回す
`roots[l]`と`roots[r]`の差分を取る（オフバイワン）	区間の左端の扱いが1個ずれている	区間$[l,r]$には`roots[r]`と`roots[l-1]`の差分を使う
再帰の深さ制限に引っかかる	Pythonのデフォルト再帰制限が低い	`sys.setrecursionlimit`を大きく設定する

次のステップ

発展: 同じ構造で「区間内で$x$以下の値の個数」を$O(\log(\max A))$で求められることを確認する
発展: マージソート木との比較（メモリ使用量・クエリ速度のトレードオフ）
次回予告: 重心分解（Centroid Decomposition）— 木上の距離が$K$以下の頂点対を数える

自己評価

完全理解おおむね理解要復習

Day 104-Q1 — 永続セグメント木（Persistent Segment Tree）

問題