Day 088-Q3 — Sqrt Tree（平方根木・$O(1)$ 区間最小値クエリ）

問題

長さ $N$ の整数列 $A$（更新なし）が与えられる。$Q$ 個のクエリ l r に対し $\min(A_l,\dots,A_r)$（$0$-indexed、両端含む）を各クエリ $O(1)$ で答えよ。

入出力例

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

1
1
3

概念図: ブロック内前計算 + ブロック間 Sparse Table

ヒント

B = int(math.isqrt(n)) + 1
within = []
for bk in range(num_blocks):
    s, e = bk*B, min(n, bk*B+B)
    table = [[0]*(e-s) for _ in range(e-s)]
    for i in range(e-s):
        cur = a[s+i]; table[i][i] = cur
        for j in range(i+1, e-s):
            cur = min(cur, a[s+j]); table[i][j] = cur
    within.append(table)

模範解答

import sys
import math

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

    B = max(1, int(math.isqrt(n)) + 1)
    num_blocks = (n + B - 1) // B

    within = []
    for bk in range(num_blocks):
        s = bk * B
        e = min(n, s + B)
        length = e - s
        table = [[0] * length for _ in range(length)]
        for i in range(length):
            cur = a[s + i]
            table[i][i] = cur
            for j in range(i + 1, length):
                cur = min(cur, a[s + j])
                table[i][j] = cur
        within.append(table)

    block_min = []
    for bk in range(num_blocks):
        s = bk * B
        e = min(n, s + B)
        block_min.append(within[bk][0][e - s - 1])

    sp = [block_min[:]]
    k = 1
    while (1 << k) <= num_blocks:
        prev = sp[-1]
        half = 1 << (k - 1)
        cur = [min(prev[i], prev[i + half]) for i in range(num_blocks - (1 << k) + 1)]
        sp.append(cur)
        k += 1

    def block_range_min(l, r):
        length = r - l + 1
        k = length.bit_length() - 1
        return min(sp[k][l], sp[k][r - (1 << k) + 1])

    def query(l, r):
        bl, br = l // B, r // B
        if bl == br:
            return within[bl][l - bl * B][r - bl * B]
        left_end = min(n, bl * B + B) - 1
        left_part = within[bl][l - bl * B][left_end - bl * B]
        right_start = br * B
        right_part = within[br][0][r - right_start]
        ans = min(left_part, right_part)
        if bl + 1 <= br - 1:
            ans = min(ans, block_range_min(bl + 1, br - 1))
        return ans

    out = []
    for _ in range(q):
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        out.append(str(query(l, r)))
    print('\n'.join(out))

solve()

計算量: 前処理 $O(N\sqrt N)$、クエリ $O(1)$。

Step-by-Step 解説

Step 1: ブロック分割と全区間前計算

$B\approx\sqrt N$ で分割し、各ブロック内のすべての部分区間の min を前計算する（$O(N\sqrt N)$）。

Step 2: ブロック集約 + Sparse Table

各ブロック全体の min を集約した配列に Sparse Table を構築（ブロック数 $O(\sqrt N)$ なので軽い）。

Step 3: クエリ処理の3分割

同一ブロック内なら前計算済みテーブルを直接引く。またがる場合は左端・右端・中間の3値の min を取る。

Step 4: 真の Sqrt Tree への発展

本問はブロック内を $O(B^2)$ で愚直計算する簡略版。本格的な Sqrt Tree はブロックを再帰的に分割し前処理を $O(N\log\log N)$ まで削減する。

よくあるミス

次のステップ

• 発展問題: 本格的な再帰 Sqrt Tree（$O(N\log\log N)$ 前処理）の実装
• 応用: 更新ありの場合はブロック単位再構築（$O(\sqrt N)$ 更新）

自己評価