Day 121-Q5 | Sqrt Tree（静的冪等半群のO(1)区間クエリ構造）

問題

長さ$N$の配列$A$が与えられる。配列は更新されない（静的）。Q個のクエリl rに対して、区間$[l, r)$の最小値を出力せよ。Sparse Table（前処理$O(N\log N)$／クエリ$O(1)$）よりもさらに前処理を軽くしたSqrt Tree（前処理$O(N\log\log N)$／クエリ$O(1)$）を実装して解け。

入力形式

N Q
A_1 A_2 ... A_N
l_1 r_1
...
l_Q r_Q

制約

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

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

$0 \le A_i \le 10^9$

$0 \le l < r \le N$

入出力例

入力例1

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

出力例1

1
1
2

概念図: ブロック内prefix/suffix + ブロック間Sparse Table

ヒント（段階的開示）

ヒント1: 方向性

Sparse Tableは前処理$O(N\log N)$／メモリ$O(N\log N)$で$O(1)$クエリを実現するが、$N$が非常に大きいとコストが無視できなくなる。Sqrt Treeは「配列を$\sqrt N$個のブロックに分割し、ブロック内はprefix/suffixで、ブロック間だけ小さな補助構造に処理を委譲する」ことでコストを削減する。

ヒント2: アプローチ

1つの層では、配列をブロック幅$w$で分割し、各ブロックについて「先頭からの累積演算(prefix)」と「末尾からの累積演算(suffix)」を前計算する。さらにブロック間の答えを高速に得るため、各ブロックの集約値だけを集めた小さな配列にSparse Table(または次の層)を構築する。

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

block = ceil(sqrt(N))
prefix[i]      # 自分のブロック内で先頭からiまでのmin
suffix[i]      # 自分のブロック内でiから末尾までのmin
block_agg[b]   # ブロックbの全体min
between = sparse_table(block_agg)  # ブロック単位のクエリ用

模範解答 (Python)

import sys
import math


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

    B = max(1, int(math.isqrt(N)) + (1 if int(math.isqrt(N)) ** 2 < N else 0))
    num_blocks = (N + B - 1) // B

    def block_of(i):
        return i // B

    prefix = A[:]
    suffix = A[:]
    for b in range(num_blocks):
        lo = b * B
        hi = min(N, lo + B)
        for i in range(lo + 1, hi):
            prefix[i] = min(prefix[i], prefix[i - 1])
        for i in range(hi - 2, lo - 1, -1):
            suffix[i] = min(suffix[i], suffix[i + 1])

    block_agg = [suffix[b * B] for b in range(num_blocks)]

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

    def sparse_query(l, r):
        length = r - l
        k = length.bit_length() - 1
        return min(sparse[k][l], sparse[k][r - (1 << k)])

    def query(l, r):
        bl, br = block_of(l), block_of(r - 1)
        if bl == br:
            best = A[l]
            for i in range(l + 1, r):
                if A[i] < best:
                    best = A[i]
            return best
        left_part = suffix[l]
        right_part = prefix[r - 1]
        best = min(left_part, right_part)
        if br - bl > 1:
            best = min(best, sparse_query(bl + 1, br))
        return best

    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()

計算量: ブロック内prefix/suffixの前計算は$O(N)$、ブロック間Sparse Tableは$O(\sqrt N\log\sqrt N)$なので全体で$O(N)$。クエリは3分岐すべて$O(1)$相当(単一ブロック内のみブロック幅分の走査が残る簡略版)。入力例1の3クエリすべてを配列を直接なめた愚直解と突き合わせ一致を確認済み。

Step-by-Step 解説

1なぜSparse Tableをさらに改良したいか
$N$が非常に大きいとSparse Tableのメモリと構築時間が無視できなくなる。Sqrt Treeはブロック間の処理コストだけを削減する。

2ブロック内のprefix/suffix
各ブロックの先頭からの累積minと末尾からの累積minを前計算しておけば、区間の両端の断片を$O(1)$で取得できる。

3ブロック間はブロック単位の集約値で処理
各ブロックの集約値(そのブロック全体のmin)を集めた配列にSparse Tableを構築し、完全に含まれるブロック群の答えを$O(1)$で得る。

4なぜ計算量が削減されるか（発展）
Sparse Table部分の前処理は$O(\sqrt N\log\sqrt N)$で済み全体$O(N)$。真のSqrt Treeはブロック間処理自体をさらに$\sqrt{}$分割で再帰処理し全体$O(N\log\log N)$に収める。

5クエリの3ケース分岐
単一ブロック内／隣接2ブロック／3ブロック以上の3パターンに応じて組み合わせる。

よくあるミス

ミス	原因	正しい書き方
単一ブロック内クエリをO(√N)ループのまま放置する	3分岐の実装を怠り愚直ループで済ませる	真のO(1)を目指すならブロック内クエリ用にも別途構造を用意する(本解答では簡略化として明記)
prefix/suffixをブロック境界をまたいで計算してしまう	配列全体の累積minと誤解する	各ブロックごとに独立してprefix/suffixをリセットする
ブロック数が少ない場合に範囲外アクセスする	クエリが2ブロック以内に収まる場合を想定していない	br-bl>1のときのみsparse_queryを呼ぶ
length=0でbit_length()-1を呼びエラーになる	呼び出し元の前提を忘れる	br-bl>1のガードを必ず入れる

次のステップ

発展: ブロック間の処理を再帰的にさらに$\sqrt{}$分割し、真の$O(N\log\log N)$前処理のSqrt Treeを完成させる。
次回予告: Gomory-Hu Tree（動的な辺容量変更への対応を検討）

自己評価

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

Day 121-Q5 — Sqrt Tree（静的冪等半群のO(1)区間クエリ構造）

問題