Day 098-Q2 | 永続Trie（Persistent Binary Trie）

問題

長さ $N$ の非負整数列 $A_1, \dots, A_N$（$0 \le A_i < 2^{30}$）が与えられる。累積XOR $P_0=0,\ P_i = P_{i-1}\oplus A_i$ を定義する。

$Q$ 個のクエリ l r x が与えられる。各クエリについて $\displaystyle\max_{l-1 \le i \le r} (P_i \oplus x)$ を出力せよ。

これは 永続Trie（Persistent Binary Trie） を用いることで、各クエリを $O(\log(\max A))$ で処理できる古典的な区間XOR最大値問題である。$P_0,\dots,P_N$ を1つずつ増分挿入しながらバージョン $0,\dots,N$ のTrieを作り、各ノードに「最後に更新した挿入インデックス」を持たせることで範囲制限クエリを実現する。

入力形式

N Q
A_1 A_2 ... A_N
query_1
:
query_Q

制約

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

$0 \le A_i, x < 2^{30}$

$1 \le l \le r \le N$

入出力例

入力例1

出力例1

19
15

$P_0=0,P_1=3,P_2=9,P_3=12,P_4=21$。クエリ1は $i\in\{0,1,2,3,4\}$ から最大値（$21\oplus6=19$）、クエリ2は $i\in\{1,2,3\}$ から最大値（$9\oplus6=15$）。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「配列中の要素とXOR最大になるものを探す」だけならTrie1本で $O(\log(\max A))$ だが、今回は「区間 $[l-1,r]$ に限定する」制約がある。挿入順とインデックスの単調性をどう使えば範囲制限を実現できるか考えよ。

ヒント2: アプローチ

挿入をインデックス順に行い、挿入するたびにTrie全体を新しいバージョンとして「パスコピー（persistence）」する。各ノードに「そのノードを通過した最大の挿入インデックス」を持たせておけば、バージョン $r$ のTrieから探索を始めて「部分木の最大インデックスが $l-1$ 以上のノードだけ」を辿ることで範囲 $[l-1,r]$ に限定できる。

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

class Node:
    __slots__ = ('child', 'max_idx')
    def __init__(self):
        self.child = [None, None]
        self.max_idx = -1

def query_max_xor(root, lo, x):
    cur = root
    num = 0
    for b in range(29, -1, -1):
        bit = (x >> b) & 1
        want = 1 - bit  # 反対のビットを選べばXORが最大化される
        nxt = cur.child[want]
        if nxt is not None and nxt.max_idx >= lo:
            num = (num << 1) | want
            cur = nxt
        else:
            cur = cur.child[bit]
            num = (num << 1) | bit
    return num ^ x

各ビットで「反対ビットの子が存在し、かつその部分木に範囲内のインデックスが含まれるか」を確認するのが鍵。

模範解答 (Python)

import sys


class Node:
    __slots__ = ('child', 'max_idx')

    def __init__(self):
        self.child = [None, None]
        self.max_idx = -1


B = 29  # A_i, x < 2^30


def insert(prev_root, idx, val):
    new_root = Node()
    cur = new_root
    prev = prev_root
    for b in range(B, -1, -1):
        bit = (val >> b) & 1
        other = 1 - bit
        cur.child[other] = prev.child[other] if prev is not None else None
        nxt = Node()
        cur.child[bit] = nxt
        cur.max_idx = idx
        cur = nxt
        prev = prev.child[bit] if prev is not None else None
    cur.max_idx = idx
    return new_root


def query_max_xor(root, lo, x):
    cur = root
    num = 0
    for b in range(B, -1, -1):
        bit = (x >> b) & 1
        want = 1 - bit
        nxt = cur.child[want]
        if nxt is not None and nxt.max_idx >= lo:
            num = (num << 1) | want
            cur = nxt
        else:
            cur = cur.child[bit]
            num = (num << 1) | bit
    return num ^ x


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [int(data[idx + i]) for i in range(n)]
    idx += n

    roots = [None] * (n + 1)
    roots[0] = insert(None, 0, 0)
    p = 0
    for i in range(1, n + 1):
        p ^= a[i - 1]
        roots[i] = insert(roots[i - 1], i, p)

    out = []
    for _ in range(q):
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        x = int(data[idx]); idx += 1
        out.append(str(query_max_xor(roots[r], l - 1, x)))

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


solve()

計算量: 挿入・クエリともに $O(\log(\max A))$。全体で $O((N+Q)\log(\max A))$、メモリは $O(N\log(\max A))$。

Step-by-Step 解説

1累積XOR配列の構築
区間XOR最大化クエリは「$P_{l-1}$ から $P_r$ までの中から $x$ とのXORが最大のものを選ぶ」問題に帰着できる。

2永続Trieへの逐次挿入
挿入のたびに新しいパスだけ新規作成し、それ以外の枝は前バージョンと共有する。1挿入あたり $O(\log(\max A))$ ノード追加。

3max_idxによる範囲フィルタ
max_idx >= lo の確認により、インデックス $<$ lo しか含まない部分木を除外する。

4貪欲なビット選択
各ビットで $x$ と反対のビットを優先選択（上位ビットほど寄与が大きいため）。範囲制約で選べない場合は同じビットへ。

よくあるミス

ミス	原因	正しい書き方
`max_idx`の更新をルートのみに行う	パス全体で更新が必要なことを見落とす	挿入パス上の全ノードに `max_idx=idx` を設定
クエリ範囲を `[l,r]` のまま渡す	累積XORへの変換を忘れる	`roots[r]` を使い、下限は `l-1` を渡す
反対ビットの子の存在だけ確認しmax_idxを見ない	古いバージョンの枝が範囲外の可能性を無視	必ず `nxt.max_idx >= lo` も確認する
再帰でTrie構築しRecursionError	30段の再帰でも上限に近づく場合がある	挿入・クエリはループで実装する

次のステップ

発展: 挿入だけでなく「削除」も行いたい場合の永続Trie＋バージョン管理の設計
発展: 2次元平面上の点集合に対する「XOR最大値」を可能にするTrie＋座標分割の融合
次回予告: MST-doubling 2近似法（巡回セールスマン問題の近似アルゴリズム）

自己評価

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

Day 098-Q2 — 永続Trie（Persistent Binary Trie・区間XOR最大値クエリ）

問題