Day 154-Q3 | 永続Binary Trie（Persistent XOR Trie）

問題

長さ $N$ の非負整数列 $a_1, \dots, a_N$ が与えられる。$Q$ 個のクエリ l r x に対し、$a_l, a_{l+1}, \dots, a_r$ の中から1つ選んだ要素 $a_i$ と $x$ の XOR（$a_i \oplus x$）の最大値を求めよ。

入力形式

N
a_1 a_2 ... a_N
Q
l_1 r_1 x_1
...
l_Q r_Q x_Q

制約

$1 \le N, Q \le 2 \times 10^5$

$0 \le a_i, x_i < 2^{30}$

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

入出力例

入力例1

出力例1

13
14

概念図：バージョン間のcnt差分による枝の判定

ヒント（段階的開示）

ヒント1（方向性）

区間を固定しない（$l=1,r=N$ 固定）なら、要素をすべて1本の二分トライに挿入し、$x$ の各ビットの反対方向を貪欲に選べば $O(30)$ で最大XORが求まる。問題は「区間 $[l,r]$ に限定する」部分をどう扱うかである。

ヒント2（アプローチ）

区間和を「累積和の引き算」で求めるのと同じ発想を、二分トライの「部分木に含まれる要素の個数（cnt）」に適用する。$i$ 番目まで挿入した状態のトライをバージョン $i$ として保持し（挿入経路上のノードだけ新規作成する永続化）、クエリでは root[r] と root[l-1] を同時に辿りながら各ビットで $cnt_r - cnt_{l-1}$ が正かどうかで進む方向を決める。

ヒント3（誘導）

def query(root_r, root_l1, x):
    u, v = root_r, root_l1
    ans = 0
    for b in range(29, -1, -1):
        want = 1 - ((x >> b) & 1)
        cu = cnt[child[u][want]]
        cv = cnt[child[v][want]]
        if cu - cv > 0:
            ans |= (1 << b)
            u, v = child[u][want], child[v][want]
        else:
            same = 1 - want
            u, v = child[u][same], child[v][same]
    return ans

模範解答 (Python)

import sys
input = sys.stdin.readline

B = 30  # ビット幅（本問の制約: a_i, x < 2^30）


def main():
    N = int(input())
    a = list(map(int, input().split()))

    child = [[0, 0]]
    cnt = [0]

    def new_node():
        child.append([0, 0])
        cnt.append(0)
        return len(cnt) - 1

    def insert(prev, val):
        root = new_node()
        u, p = root, prev
        for b in range(B - 1, -1, -1):
            bit = (val >> b) & 1
            nu = new_node()
            other = 1 - bit
            child[u][other] = child[p][other] if p else 0
            child[u][bit] = nu
            cnt[nu] = (cnt[child[p][bit]] if p else 0) + 1
            u = nu
            p = child[p][bit] if p else 0
        return root

    roots = [0]
    for v in a:
        roots.append(insert(roots[-1], v))

    def query(l, r, x):
        u, v = roots[r], roots[l - 1]
        ans = 0
        for b in range(B - 1, -1, -1):
            xb = (x >> b) & 1
            want = 1 - xb
            cu = cnt[child[u][want]] if u else 0
            cv = cnt[child[v][want]] if v else 0
            if cu - cv > 0:
                ans |= (1 << b)
                u = child[u][want] if u else 0
                v = child[v][want] if v else 0
            else:
                u = child[u][xb] if u else 0
                v = child[v][xb] if v else 0
        return ans

    Q = int(input())
    out = []
    for _ in range(Q):
        l, r, x = map(int, input().split())
        out.append(str(query(l, r, x)))
    print('\n'.join(out))


main()

Step-by-Step 解説

1数値の範囲
入力例の値は $\{3,8,1,12,7\}$ や $x=5,15$ のように16未満（4ビット）に収まり、手計算での検証がしやすい。アルゴリズムは $B=30$ ビットのまま動作する（上位ビットは常に0）。

2クエリ 2 4 5 をブルートフォースで検算
区間 $[2,4]$ は $a_2=8,a_3=1,a_4=12$。$x=5$ とのXORは $13, 4, 9$。最大は 13（$a_2=8$）で出力例1行目と一致。

3クエリ 1 5 15 をブルートフォースで検算
区間 $[1,5]$ は全要素。$x=15$ とのXORは $12,7,14,3,8$。最大は 14（$a_3=1$）で出力例2行目と一致。

4永続トライが一致する理由
$cnt_r - cnt_{l-1}$ は「$a_l,\dots,a_r$ の中でその部分木に入る要素の個数」を正確に表す。差が1以上ならその枝に区間内の要素が実在するので貪欲に$x$の反対ビット方向へ進んでよく、Step2・Step3の結果と一致することが保証される。

よくあるミス

ミス	原因	正しい書き方
クエリをl,rのバージョンで比較してしまう	累積和の「引く方は1つ手前」という定石を忘れる	区間[l,r]は必ずroots[r]とroots[l-1]のペアで扱う
u=0（空ノード）のガードを忘れる	番兵ノード0の子アクセスの存在チェック省略	uが空かどうかを明示的にチェックしてからchild[u][...]にアクセスする
挿入のたびにトライ全体をコピーする	「永続化＝スナップショットを丸ごと保存」という誤解	更新経路（根から葉までのB個のノード）だけを新規作成し他は前バージョンと共有
ビット幅Bをサンプルの見た目に合わせて縮める	サンプル値の小ささに引きずられる	Bは問題の制約（本問は2^30未満）に合わせて固定する
xと同じビットを辿ってしまう	XOR最大化の方向を勘違い	XOR最大化には常にxのビットと異なる方向へ進む

次のステップ

発展: 同じ永続トライで「区間内で $k$ 番目に大きい $a_i \oplus x$」を求めるクエリ（各ビットでの差分カウントを使った二分探索）に拡張する。
次回予告: Welzl's Algorithm（最小包含円・乱択増分法）

自己評価

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

Day 154-Q3 — 永続Binary Trie（Persistent XOR Trie）

問題