Day 109-Q5 — Interval Tree（区間木・拡張BSTによる点スタビングクエリ）

2026-08-01 赤色 Master / Phase 8+ ★★★★★★★★★ 右端点最大値で拡張したBSTによる重複区間クエリ

問題

$N$ 個の区間 $[l_i, r_i]$ が与えられる。これらを Interval Tree（区間木）——各ノードが「自分を根とする部分木に含まれる区間の右端点の最大値」を追加情報として持つ拡張二分探索木——に構築せよ。

構築後、$Q$ 個のクエリ点 $x_1,\dots,x_Q$ それぞれについて、$x$ を含む区間（$l_i \le x \le r_i$ を満たす区間）の個数を出力せよ。

入力形式

N
l_1 r_1
l_2 r_2
...
l_N r_N
Q
x_1
x_2
...
x_Q

制約

$1 \le N, Q \le 2\times10^5$
$0 \le l_i \le r_i \le 10^9$
$0 \le x_j \le 10^9$

入出力例

入力例1

4
1 5
3 7
10 12
6 9
3
4
8
11

出力例1

2
1
1

区間は[1,5],[3,7],[10,12],[6,9]。x=4を含むのは[1,5]と[3,7]の2個。x=8を含むのは[6,9]の1個。x=11を含むのは[10,12]の1個。

概念図: 右端点最大値による枝刈り探索

中央値分割で構築した拡張BST（各ノードにmax_rを付与） [6,9] max_r=12 [3,7] max_r=7 [10,12] max_r=12 [1,5] max_r=5 query(x=8): 左部分木max_r=7<8なので[3,7]側は枝刈り、[6,9]と[10,12]側のみ探索

ヒント（段階的開示）

ヒント1: 方向性
「ある点$x$を含む区間を数える」というクエリを、区間集合全体を毎回走査して素朴に判定すると$O(N)$かかり、$Q$回のクエリで$O(NQ)$になってしまう。値の範囲に対するクエリに強いセグメント木は、区間そのものの集合を扱う用途にはそのままでは使いにくい。区間の集合を効率よく格納し、点クエリに高速に答えられる専用のデータ構造が必要になる。
ヒント2: アプローチ
Interval Tree（CLRSで紹介される古典的な区間木）は、区間の左端点$l_i$でソートした通常の二分探索木を土台にし、各ノードに「自分を根とする部分木に含まれる区間の右端点の最大値」（max_r）を追加情報として持たせる。

クエリ点$x$に対して探索するとき：
- 左の子部分木は、max_r >= xの場合のみ再帰する（それ未満なら部分木内のどの区間も$x$を含み得ない）。
- 現在のノード自身は$l\le x\le r$かどうかを直接判定してカウントする。
- 右の子部分木は、「現在のノードの左端点が$x$以下」かつ「max_r >= x」の場合のみ再帰する（BSTの構造上、右部分木の全区間の左端点は現在のノードの左端点以上）。
ヒント3: 誘導（コード骨格） 
def query(node, x):
    if node is None:
        return 0
    cnt = 0
    if node.left and node.left.max_r >= x:
        cnt += query(node.left, x)
    if node.l <= x <= node.r:
        cnt += 1
    if node.l <= x and node.right and node.right.max_r >= x:
        cnt += query(node.right, x)
    return cnt

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    intervals = []
    for _ in range(n):
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        intervals.append((l, r))
    q = int(data[idx]); idx += 1
    queries = []
    for _ in range(q):
        queries.append(int(data[idx])); idx += 1

    intervals.sort()  # 左端点でソートしてBSTの土台にする

    L = [0] * n
    R = [0] * n
    MAXR = [0] * n
    LEFT = [-1] * n
    RIGHT = [-1] * n

    def build(lo, hi):
        # intervals[lo:hi) を中央値分割でバランスさせながら木を構築する
        if lo >= hi:
            return -1
        mid = (lo + hi) // 2
        L[mid], R[mid] = intervals[mid]
        LEFT[mid] = build(lo, mid)
        RIGHT[mid] = build(mid + 1, hi)
        mx = R[mid]
        if LEFT[mid] != -1:
            mx = max(mx, MAXR[LEFT[mid]])
        if RIGHT[mid] != -1:
            mx = max(mx, MAXR[RIGHT[mid]])
        MAXR[mid] = mx
        return mid

    root = build(0, n)

    def query(node, x):
        if node == -1:
            return 0
        cnt = 0
        if LEFT[node] != -1 and MAXR[LEFT[node]] >= x:
            cnt += query(LEFT[node], x)
        if L[node] <= x <= R[node]:
            cnt += 1
        if L[node] <= x and RIGHT[node] != -1 and MAXR[RIGHT[node]] >= x:
            cnt += query(RIGHT[node], x)
        return cnt

    out = []
    for x in queries:
        out.append(str(query(root, x)))
    print("\n".join(out))

solve()
計算量: 構築$O(N\log N)$（ソート）、各クエリは平均$O(\log N+k)$（木が中央値分割でバランスしているため最悪でも$O(\log N)$段しか高さがない）。500回のランダムな区間集合・クエリ点で全区間を毎回走査する愚直解と突き合わせるストレステストで一致を確認済み。

Step-by-Step 解説

1左端点でソートしてBSTの土台を作る
区間集合を左端点$l_i$の昇順にソートし、中央値分割によって再帰的に木を構築する（配列のインデックスをそのままノードIDとして使う）。
2各ノードに部分木内の右端点最大値を持たせる（augmentation）
左右の子を再帰的に構築した後、自分自身の右端点と左右の子のMAXRの最大値を取り記録する。これが拡張二分探索木の考え方。
3クエリは3方向の枝刈り条件で無駄な探索を省く
左部分木はMAXR[LEFT[node]] >= xのときだけ、右部分木はL[node] <= xかつMAXR[RIGHT[node]] >= xのときだけ再帰する。
4なぜ右部分木の枝刈りに「現在の左端点 <= x」が必要か
右部分木の全区間の左端点は現在のノードの左端点以上なので、もしL[node] > xであれば右部分木のどの区間も$x$を含むことは不可能である。
5セグメント木との使い分け
セグメント木は「値の範囲に対するクエリ」に強いが、「区間そのものの集合の中から、ある点を含むものを探す」用途には、区間木のように区間をノードとして格納し右端点最大値で枝刈りする設計の方が自然に対応できる。

よくあるミス

ミス原因正しい書き方
右部分木への再帰条件で「現在の左端点 <= x」を忘れるMAXR[RIGHT[node]] >= xだけで十分だと誤解してしまう右部分木の左端点が全てL[node]以上であることを利用した枝刈り条件を必ず加える
buildで中央値分割をせず連結リストのように構築してしまう再帰の分割点を考えずに実装すると木が偏るmid=(lo+hi)//2で常に中央値をルートに選び、木の高さを$O(\log N)$に保つ
MAXRの更新で自分自身の右端点を含め忘れる左右の子のMAXRだけを比較して自分のRを無視してしまうmx = R[mid]から始めて左右の子のMAXRと比較する
座標が大きい（$10^9$程度）ことに引きずられて座標圧縮が必要だと思い込むセグメント木の文脈に慣れていると反射的に検討してしまう区間木は区間そのものをノードとして扱うため座標の値域の大きさはノード数に影響せず座標圧縮は不要

次のステップ

  • 発展: 点クエリだけでなく「区間$[ql,qr]$と重なる全区間を数える」クエリに拡張する
  • 発展: 動的な区間の追加・削除に対応させる（平衡を保つには赤黒木やAVL木、Treapベースの実装に置き換える）
  • 発展: 区間スケジューリング問題と組み合わせ、区間木で高速に矛盾判定を行うスケジューラを設計する

自己評価

自分の回答

気づき・メモ