Day 053-Q3 | Disjoint Sparse Table（任意半群の静的RMQ・O(1)クエリ）

問題

長さ $N$ の整数列 $A = (A_1, \ldots, A_N)$ と $Q$ 個のクエリ $(l_i, r_i)$ が与えられる。各クエリに対し $A_{l_i} \oplus A_{l_i+1} \oplus \cdots \oplus A_{r_i}$ を求めよ（$\oplus$ は XOR）。

制約: $N, Q \le 10^7$。前処理 $O(N \log N)$、各クエリ $O(1)$ でなければ間に合わない。

制約

パラメータ	範囲
$N$	$1 \le N \le 10^7$
$Q$	$1 \le Q \le 10^7$
$A_i$	$0 \le A_i < 2^{30}$
$l, r$	$1 \le l \le r \le N$
時間制限	3秒

入出力例

入力例 1

8 4
3 1 4 1 5 9 2 6
1 8
2 5
3 7
4 4

出力例 1

[1,8]: 3^1^4^1^5^9^2^6=11。[2,5]: 1^4^1^5=3。[3,7]: 4^1^5^9^2=13。[4,4]: 1。

概念図: Disjoint Sparse Table のレベル構造

ヒント（段階的開示）

ヒント1: 方向性

通常の Sparse Table は冪等演算（min/max/gcd）専用。XOR は $a \oplus a = 0$ なので区間重複で値が消える。Disjoint Sparse Table はブロック内で中心から外向きに累積し、クエリ時に重複なく2要素を合成する。

ヒント2: アプローチ

レベル $k$: ブロック幅 $2^k$。各ブロックの「左半部末尾」から左向き、「右半部先頭」から右向きに累積
クエリ $[l, r]$: $k = \text{bit\_length}(l \oplus r) - 1$ で $l$ と $r$ が異なるブロックに属するレベルを特定
$\text{dst}[k][l] \oplus \text{dst}[k][r]$ が答え（$l = r$ のときは $A[l]$）

ヒント3: コード骨格

LOG = N.bit_length()
dst = [[0]*N for _ in range(LOG)]
dst[0] = A[:]

for k in range(1, LOG):
    bw = 1 << k    # ブロック幅
    half = bw >> 1  # = 2^(k-1)
    i = half
    while i < N:
        # 左半部末尾から左へ（中心 i-1 から左）
        dst[k][i-1] = A[i-1]
        for j in range(i-2, max(i-bw, -1), -1):
            dst[k][j] = A[j] ^ dst[k][j+1]
        # 右半部先頭から右へ（中心 i から右）
        if i < N:
            dst[k][i] = A[i]
            for j in range(i+1, min(i+half, N)):
                dst[k][j] = dst[k][j-1] ^ A[j]
        i += bw

# クエリ
def query(l, r):  # 0-indexed
    if l == r: return A[l]
    k = (l ^ r).bit_length() - 1
    return dst[k][l] ^ dst[k][r]

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.buffer.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

    # Disjoint Sparse Table 構築
    LOG = max(1, N.bit_length())
    dst = [A[:]]  # dst[0] = A

    for k in range(1, LOG):
        bw = 1 << k
        half = bw >> 1
        level = [0] * N
        i = half
        while i < N:
            # 左半部末尾(i-1)から左へ
            level[i-1] = A[i-1]
            j = i - 2
            while j >= i - bw and j >= 0:
                level[j] = A[j] ^ level[j+1]
                j -= 1
            # 右半部先頭(i)から右へ
            if i < N:
                level[i] = A[i]
                j = i + 1
                while j < i + half and j < N:
                    level[j] = level[j-1] ^ A[j]
                    j += 1
            i += bw
        dst.append(level)

    # クエリ処理
    out = []
    for _ in range(Q):
        l = int(data[idx]) - 1; idx += 1  # 0-indexed
        r = int(data[idx]) - 1; idx += 1
        if l == r:
            out.append(A[l])
        else:
            k = (l ^ r).bit_length() - 1
            out.append(dst[k][l] ^ dst[k][r])

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

Step-by-Step 解説

1なぜ通常のSparse Tableが使えないか
通常のSparse Table: クエリ $[l,r]$ を $k = \lfloor \log_2(r-l+1) \rfloor$ として $\text{op}(\text{st}[k][l], \text{st}[k][r-2^k+1])$ で計算。この2区間は重複する。min/max は重複しても同値（冪等性）だが、XOR は $a \oplus a = 0$ で値が消える。

2Disjoint Sparse Table のブロック構造
レベル $k$ でブロック幅 $2^k$。各ブロック内で中心から外向きに累積を計算。クエリ $[l,r]$ で $l$ と $r$ が異なるブロックに属するレベル $k$ を選ぶと、$\text{dst}[k][l]$ は「$l$ からその中心まで」、$\text{dst}[k][r]$ は「$r$ からその中心まで」の累積。合成すると $[l,r]$ 全体が重複なく覆われる。

3$k = \text{bit\_length}(l \oplus r) - 1$ の意味
$l \oplus r$ の最上位ビット位置が、$l$ と $r$ が初めて異なるビット位置 = 両者が異なるブロックに属する最小レベル。このレベルで $l$ はブロックの右半分、$r$ は左半分（または逆）に属する。

4$O(1)$ クエリの実現
テーブル参照2回 + XOR1回のみ。前処理で $\text{dst}[k][l]$ と $\text{dst}[k][r]$ を用意しているため、クエリごとの計算は定数時間。

計算量

前処理: $O(N \log N)$ 時間・空間
各クエリ: $O(1)$ — テーブル参照2回 + XOR1回
全体: $O(N \log N + Q)$
通常のSparse Table との比較: 前処理は同じ $O(N \log N)$、クエリは両方 $O(1)$
違い: DST は任意半群に適用可能（通常ST は冪等性が必要）

よくあるミス

ミス	原因	正しい書き方
$l = r$ のケースを忘れる	$l \oplus r = 0$ で bit_length=0 になる	`if l == r: return A[l]`
中心の定義ずれ	ブロック幅 $2^k$ のどこが中心か	左半部末尾 = `i-1`、右半部先頭 = `i`
$k$ の計算ミス	`(l^r).bit_length()` は 1以上	$- 1$ を忘れずに
大規模入力で TLE	通常の `input()` が遅い	`sys.stdin.buffer.read()` で一括読み込み

次のステップ

発展問題: 動的配列（更新あり）の場合はSegTreeが必要。Disjoint Sparse Tableでは対処できない理由を説明せよ。
関連: 冪等半群（GCD, LCM, min, max）の場合は通常のSparse Tableが最適（定数が小さい）。
応用: 文字列の区間ハッシュ（乗算モノイド）に DST を適用する。

自己評価

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