Day 130-Q3 — Interval Tree（拡張BSTによる区間被覆判定）

2026-08-22 赤色 Master / Phase 8+ ★★★★★★★★★ 部分木max_endによるオンライン区間検索

問題

$Q$個のクエリをオンラインで処理する。クエリは2種類: ADD l r（区間$[l,r]$を集合に追加）、QUERY p（現時点で点$p$を含む区間が1つでもあればYES l r、なければNOを出力）。区間の削除はない。左端をキーとするBSTに各部分木の最大右端(max_end)を持たせた区間木で処理せよ。

入力形式

Q
op_1
op_2
...
op_Q

制約

$1 \le Q \le 200000$
$0 \le l \le r \le 10^9$, $0 \le p \le 10^9$

入出力例

入力例1

5
ADD 1 5
ADD 10 20
QUERY 3
QUERY 7
QUERY 15

出力例1

YES 1 5
NO
YES 10 20

概念図

QUERY p: max_endで左部分木を探す価値を判定 [10,20] max=20 [1,5] max=5 (なし) QUERY 7: 根[10,20]は7を含まない → 左max_end=5<7なので左は探索不要 → 右へ → 一致なしNO

ヒント（段階的開示）

ヒント1（方向性）

毎回全区間走査だとO(Q²)。左端をキーにしたBSTに各ノードの部分木内の右端最大値(max_end)を持たせると探索を大幅に枝刈りできる。

ヒント2（アプローチ）

現ノードの区間がpを含まなくても、左部分木のmax_end≥pなら左のどこかにpを覆う候補が残っている可能性がある。左のmax_end<pなら左は絶対に無駄なので右だけ見ればよい。

ヒント3（誘導） 
def query(node, p):
    if node is None:
        return None
    if node.l <= p <= node.r:
        return (node.l, node.r)
    if node.left is not None and node.left.max_end >= p:
        return query(node.left, p)
    return query(node.right, p)

模範解答 (Python)

import sys
sys.setrecursionlimit(300000)


class Node:
    __slots__ = ('l', 'r', 'max_end', 'left', 'right')

    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.max_end = r
        self.left = None
        self.right = None


def insert(node, l, r):
    if node is None:
        return Node(l, r)
    if l < node.l:
        node.left = insert(node.left, l, r)
    else:
        node.right = insert(node.right, l, r)
    if r > node.max_end:
        node.max_end = r
    return node


def query(node, p):
    while node is not None:
        if node.l <= p <= node.r:
            return (node.l, node.r)
        if node.left is not None and node.left.max_end >= p:
            node = node.left
        else:
            node = node.right
    return None


def main():
    data = sys.stdin.read().split()
    idx = 0
    q = int(data[idx]); idx += 1

    root = None
    out = []
    for _ in range(q):
        op = data[idx]; idx += 1
        if op == 'ADD':
            l = int(data[idx]); r = int(data[idx + 1]); idx += 2
            root = insert(root, l, r)
        else:
            p = int(data[idx]); idx += 1
            res = query(root, p)
            if res is None:
                out.append('NO')
            else:
                out.append(f'YES {res[0]} {res[1]}')

    print('\n'.join(out))


main()

Step-by-Step 解説

1なぜ左端をキーにするか
区間集合を検索しやすい形にするため左端の大小関係でBSTを組む。これだけではpを含む区間は探せない。
2max_endの意味
あるノードを根とする部分木の全区間の右端の最大値。挿入時は経路上の全祖先を更新する。
3クエリの枝刈り
現ノードがpを含まなくても左部分木に「左端は小さいが右端が大きい」区間が眠っている可能性がある。node.left.max_end>=pがその判定条件。
4右だけでよい理由
左のmax_end<pならどの区間の右端もpより小さく絶対に含まない。よって左を切り捨て右だけ見てよい。
5計算量
挿入順がランダムに近ければ期待O(log N)。最悪ケース(ソート済み挿入等)ではO(N)に劣化するので真に保証したいなら赤黒木で平衡化する。

よくあるミス

ミス原因正しい書き方
max_endの更新を経路の途中で忘れる再帰の戻り値を親に反映し忘れる挿入関数の最後で必ずnode.max_end=max(node.max_end,r)を行う
右部分木のmax_endも見て良いと勘違い左を諦めたら必ず右に行けば正しいと誤解実際には「左がダメなら右」で必ず正しい。右側の判定は不要
平衡化していないのに最悪O(log N)を期待単純BSTの弱点を見落とすソート済み入力で退化することを認識し必要ならRB木を検討
l<=p<=rの境界をl<p<rにする閉区間の境界条件ミス閉区間[l,r]としてl<=p<=rで判定する

次のステップ

  • 発展: 削除も含めたい場合はBSTを赤黒木で平衡化し、CLRS流の削除にmax_end再計算を組み込む
  • 次回予告: K番目最小全域木（Lawler法によるパーティション分割探索）

自己評価

自分の回答

気づき・メモ