Day 120-Q1 — 動的セグメント木（Dynamic Segment Tree・疎な区間XOR）

2026-08-12 赤色 Master / Phase 8+ ★★★★★★★★★ データ構造(疎な値域)・動的セグメント木・区間XOR

問題

長さ $2^{30}$ の配列 $a[0], a[1], \ldots, a[2^{30}-1]$ があり、初期状態はすべて0である。N個のクエリを順に処理せよ。

  • U p x: $a[p] \mathrel{\hat{=}} x$（$a[p]$ を x とXORする）
  • Q l r: $a[l] \oplus a[l+1] \oplus \cdots \oplus a[r-1]$ を出力する（半開区間 $[l, r)$）

入力形式

N
query_1
query_2
...
query_N

制約

$1 \le N \le 2\times10^5$
$0 \le p < 2^{30}$
$0 \le x < 2^{30}$
$0 \le l < r \le 2^{30}$

入出力例

入力例1

4
U 3 5
U 100 7
Q 0 4
Q 0 101

出力例1

5
2

区間[0,4)には点3のみが値を持つのでa[3]=5がそのまま出力される。区間[0,101)には点3と点100の両方が含まれるので5⊕7=2。

概念図: 必要なノードだけ動的に生成する

値域[0, 2^30) のうち p=3, p=100 だけが実体を持つ root [0, 2^30) L [0, 2^29) 未生成 [2^29, 2^30) p=3側 未生成 …葉まで辿ると a[3]=5 query時、未生成ノードは即座に0を返す 経路上のvalは val ^= x で更新するだけでよい

ヒント（段階的開示）

ヒント1: 方向性
値域が $2^{30}$ と巨大なので、通常のセグメント木のように配列で全ノードを確保すると $2 \times 2^{30}$ 要素になり、メモリが到底足りない。しかし実際に触れる座標（更新や範囲境界に現れる点）は高々 $N$ 個程度なので、「必要になったノードだけをその都度作る」という発想に切り替える。
ヒント2: アプローチ
セグメント木のノードを配列インデックスで管理するのをやめ、各ノードが「左の子ノード番号・右の子ノード番号・このノードが管理する区間のXOR値」を持つ構造体として動的に生成する。存在しない子は「0番（ヌルノード）」として扱い、参照されたときに初めて生成する。深さは $\log_2(2^{30}) = 30$ なので、1回の更新で高々30個の新規ノードしか作られない。
ヒント3: 誘導（コード骨格） 
left = [0]; right = [0]; val = [0]  # index 0 = 「存在しない」を表すヌルノード

def new_node():
    left.append(0); right.append(0); val.append(0)
    return len(left) - 1

def update(node, lo, hi, p, x):
    if node == 0:
        node = new_node()
    val[node] ^= x               # XORの性質上、経路上のノードすべてを ^=x するだけでよい
    if hi - lo == 1:
        return node
    mid = (lo + hi) // 2
    if p < mid:
        left[node] = update(left[node], lo, mid, p, x)
    else:
        right[node] = update(right[node], mid, hi, p, x)
    return node

def query(node, lo, hi, l, r):
    if node == 0 or r <= lo or hi <= l:
        return 0
    if l <= lo and hi <= r:
        return val[node]
    mid = (lo + hi) // 2
    return query(left[node], lo, mid, l, r) ^ query(right[node], mid, hi, l, r)

模範解答 (Python)

import sys
sys.setrecursionlimit(10000)


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    LOG = 30
    FULL = 1 << LOG

    left = [0]
    right = [0]
    val = [0]

    def new_node():
        left.append(0)
        right.append(0)
        val.append(0)
        return len(left) - 1

    root = [0]

    def update(node, lo, hi, p, x):
        if node == 0:
            node = new_node()
        val[node] ^= x
        if hi - lo == 1:
            return node
        mid = (lo + hi) // 2
        if p < mid:
            left[node] = update(left[node], lo, mid, p, x)
        else:
            right[node] = update(right[node], mid, hi, p, x)
        return node

    def query(node, lo, hi, l, r):
        if node == 0 or r <= lo or hi <= l:
            return 0
        if l <= lo and hi <= r:
            return val[node]
        mid = (lo + hi) // 2
        return query(left[node], lo, mid, l, r) ^ query(right[node], mid, hi, l, r)

    out = []
    for _ in range(N):
        t = data[idx]; idx += 1
        if t == b'U':
            p = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            root[0] = update(root[0], 0, FULL, p, x)
        else:
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            out.append(str(query(root[0], 0, FULL, l, r)))
    print('\n'.join(out))


solve()
計算量: 1回のupdate/queryは木の深さ log2(2^30)=30 に比例するのでO(30)。N回のクエリ全体でO(30N)、作成されるノード数も高々O(30N)にとどまる。ランダム300試行のstress test（配列の値域を[0,500)に絞り、単純な配列を使った愚直実装との突き合わせ）を実際に実行し、全試行で出力が一致することを確認済み。

Step-by-Step 解説

1なぜ通常のセグメント木では対応できないか
通常のセグメント木は「区間の長さ」に比例した配列を最初に確保する。値域が$2^{30}\approx10^9$もあると事前確保だけでメモリが枯渇する。一方で実際にクエリで触れる座標は$N\le2\times10^5$個程度しかない。
2ヌルノードで「未生成」を表現する
配列のインデックス0を「存在しない子」を表す特別な値として予約する。left/rightが0のままなら、その部分木はまだ一度も触られていないことを意味する。
3更新時に必要なノードだけ生成する
子ノードが0（未生成）の状態で初めてその子へ降りようとしたときにnew_node()を呼ぶ。1回の更新で根から葉までのパス上の高々30個のノードしか生成されない。
4XORの性質を利用した集約
ある葉の値がxだけ変化すると、その葉を含むすべての祖先ノードの集約値もちょうどxだけXORで変化する。経路上の各ノードでval[node]^=xするだけで正しい集約値が保たれる。
5クエリ処理
通常のセグメント木と同じ3分岐（範囲外／完全包含／部分重複）で処理する。ノードが0（未生成）なら即座に0を返してよい。

よくあるミス

ミス原因正しい書き方
ヌルノード（0番）を通常のノードとして扱い、val[0]を書き換えてしまう「未生成」を表す特別な値であることを意識しないupdateの冒頭でnode==0なら必ずnew_node()してから処理する
内部ノードで子から再帰的にvalを合成し直そうとするXORの差分伝播の性質を理解せず、通常の再構成ロジックを持ち込む経路上のノードはval[node]^=xとするだけで正しい
深い再帰でPythonのデフォルト再帰上限に達する他の処理と合わせて上限を超えるケースを想定していないsys.setrecursionlimitで余裕を持たせておく
メモリ使用量を見積もらず最初にFULLサイズの配列を確保しようとする通常のセグメント木の実装パターンをそのまま流用してしまうleft/right/valは空リストからappendで動的に伸ばす

次のステップ

  • 発展: 区間XOR代入（区間全体を特定の値にXORする一括更新）に対応する遅延伝播付き動的セグメント木を実装してみる。
  • 次回予告: 病院・研修医問題（Hospital/Residents Problem・多対一安定マッチング）

自己評価

自分の回答

気づき・メモ