Day 111-Q3 — Range Tree（2次元領域木・矩形カウントクエリ）

2026-08-03 赤色 Master / Phase 8+ ★★★★★★★★★ x座標セグ木×各ノードのソート済みy配列 O(log²N)

問題

平面上に $N$ 個の点が与えられる。$Q$ 個の矩形クエリそれぞれについて「$x_1\le x\le x_2$ かつ $y_1\le y\le y_2$」を満たす点の個数を求めよ。

入力形式

N
x_1 y_1
...
x_N y_N
Q
qx1 qx2 qy1 qy2
... (Q行)

制約

$1 \le N,Q \le 2\times10^5$
$0 \le x_i,y_i \le 10^9$
$qx1\le qx2,\ qy1\le qy2$

入出力例

入力例1

5
1 1
2 5
3 3
4 2
5 4
2
2 4 1 4
1 5 1 5

出力例1

2
5

1個目: $x\in[2,4],y\in[1,4]$ を満たすのは$(3,3)$と$(4,2)$の2点。2個目: 全区間なので5点全て。

概念図: x軸セグメント木 × 各ノードのソート済みy配列

セグメント木（x座標順）の各ノードが y のソート済みリストを持つ [0,4] y=[1,2,3,4,5] [0,2] y=[1,3,5] [3,4] y=[2,4] [0,1] y=[1,5] [2,2] y=[3] クエリ [x1,x2] を O(log N) 個のノードに分解 → 各ノードで bisect による y範囲カウント → 合計 構築: 子2つのソート済みyリストを線形マージ（Merge Sort Tree と同じ手法）

ヒント（段階的開示）

ヒント1: 方向性
「xの範囲」と「yの範囲」という2つの独立条件を同時に満たす点数えは、BITやセグ木単体では直接扱えない。1次元の構造をもう1次元分「入れ子」にする発想が核心。
ヒント2: アプローチ
点をxでソートし、その順序でセグメント木を構築。各ノードは担当区間の点のyをソートしたリストを持つ（Merge Sort Tree構築法）。クエリはxの二分探索でインデックス範囲を求め、セグ木を$O(\log N)$ノードに分解し、各ノードのyリストをbisectで数える。全体 $O(\log^2 N)$/クエリ。
ヒント3: 誘導（コード骨格） 
def _build(node, l, r):
    if l == r:
        tree[node] = [points[l][1]]
        return
    mid = (l+r)//2
    _build(node*2, l, mid); _build(node*2+1, mid+1, r)
    tree[node] = merge_sorted(tree[node*2], tree[node*2+1])  # 線形マージ

def query(x1, x2, y1, y2):
    lo, hi = bisect_index_range(x1, x2)
    # セグ木を [lo,hi] に分解しながら bisect でyの個数を数える

模範解答 (Python)

import sys, bisect

class RangeTree:
    def __init__(self, points):
        self.points = sorted(points)
        self.n = len(self.points)
        self.xs = [p[0] for p in self.points]
        self.tree = [None] * (4 * self.n) if self.n > 0 else []
        if self.n > 0:
            self._build(1, 0, self.n - 1)

    def _build(self, node, l, r):
        if l == r:
            self.tree[node] = [self.points[l][1]]
            return
        mid = (l + r) // 2
        self._build(node * 2, l, mid)
        self._build(node * 2 + 1, mid + 1, r)
        left = self.tree[node * 2]
        right = self.tree[node * 2 + 1]
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        self.tree[node] = merged

    def _count_y(self, ys, y1, y2):
        lo = bisect.bisect_left(ys, y1)
        hi = bisect.bisect_right(ys, y2)
        return hi - lo

    def query(self, x1, x2, y1, y2):
        if self.n == 0:
            return 0
        lo = bisect.bisect_left(self.xs, x1)
        hi = bisect.bisect_right(self.xs, x2) - 1
        if lo > hi:
            return 0
        return self._query(1, 0, self.n - 1, lo, hi, y1, y2)

    def _query(self, node, l, r, ql, qr, y1, y2):
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self._count_y(self.tree[node], y1, y2)
        mid = (l + r) // 2
        return (self._query(node * 2, l, mid, ql, qr, y1, y2)
                + self._query(node * 2 + 1, mid + 1, r, ql, qr, y1, y2))

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    points = []
    for _ in range(n):
        x = int(data[idx]); y = int(data[idx+1]); idx += 2
        points.append((x, y))
    rt = RangeTree(points)
    q = int(data[idx]); idx += 1
    out = []
    for _ in range(q):
        x1 = int(data[idx]); x2 = int(data[idx+1])
        y1 = int(data[idx+2]); y2 = int(data[idx+3])
        idx += 4
        out.append(str(rt.query(x1, x2, y1, y2)))
    print("\n".join(out))

solve()
計算量: 構築 $O(N\log N)$、クエリ1回 $O(\log^2 N)$、全体 $O((N+Q)\log^2 N)$。$N,Q\approx200$の2000ケースで愚直な全点走査と全結果一致を確認済み。

Step-by-Step 解説

1xでソートする
セグ木の葉順序をxの昇順に固定し、「x範囲」を連続インデックス範囲に変換する。
2各ノードにソート済みyリストを持たせる
子2つのソート済みリストを線形マージするだけで親のリストが得られ、全体構築は$O(N\log N)$。
3x範囲をノード集合に分解
通常のセグ木クエリと同様に$O(\log N)$個の完全一致ノードに分解する。
4各ノードでy範囲を二分探索
bisect_left/rightで$O(\log N)$のカウントを$O(\log N)$個のノード分合計する。
5計算量を確認
構築$O(N\log N)$、クエリ$O(\log^2 N)$。Fractional Cascadingでさらに$O(\log N)$に落とせる。

よくあるミス

ミス原因正しい書き方
x範囲の二分探索で境界がずれるbisect_left/rightの意味の取り違え上限はbisect_right(x2)-1で閉区間インデックスを求める
各ノードでyを線形走査してしまうソート済みであることを活かさないbisect_left/rightで二分探索する
セグ木のノード分解を省略する標準的な区間分解パターンの省略ql<=l and r<=qrでの打ち切りを必ず書く
sorted(left+right)でマージし$O(N\log^2N)$にしてしまうソート済み2本のマージが線形時間でできることの見落とし2ポインタで線形マージする

次のステップ

  • 発展: Fractional Cascading（Day082, Day107）でクエリを$O(\log N)$に高速化する
  • 発展: 点の追加に対応する動的Range Treeを考える
  • 発展: 3次元領域カウントへの一般化を検討する

自己評価

自分の回答

気づき・メモ