概要

指定された区間 \([L, R]\) 内の最大値と最小値の差を、複数のクエリに対して高速に求める問題です。Sparse Table（スパーステーブル）を用いることで、各クエリに \(O(1)\) で回答できます。

考察

素朴なアプローチとその問題点

最も単純な方法は、各クエリごとに区間 \([L, R]\) を順に見て最大値・最小値を求めることです。

for i in range(L-1, R):
    max_val = max(max_val, A[i])
    min_val = min(min_val, A[i])

この方法では1回のクエリに \(O(N)\) かかるため、全体で \(O(NQ)\) となります。\(N, Q \leq 10^5\) の制約下では最大 \(10^{10}\) 回の操作となり、TLE（時間制限超過） になってしまいます。

解決の方針

「区間の最大値・最小値を高速に求める」というのは、Range Minimum/Maximum Query (RMQ) と呼ばれる典型的な問題です。

重要な観察として、最大値・最小値の演算には冪等性（同じ要素を2回見ても結果が変わらない性質）があります。例えば \(\max(3, 3) = 3\) です。この性質を活かすと、Sparse Table を使って前処理 \(O(N \log N)\)、クエリ \(O(1)\) で解けます。

アルゴリズム

Sparse Table の構築

Sparse Table は「長さが \(2\) のべき乗の区間」についての情報を事前に計算しておくデータ構造です。

• \(\text{sparse\_min}[k][i]\) = 位置 \(i\) から始まる長さ \(2^k\) の区間の最小値
• \(\text{sparse\_max}[k][i]\) = 位置 \(i\) から始まる長さ \(2^k\) の区間の最大値

構築の漸化式： $\(\text{sparse\_min}[k][i] = \min(\text{sparse\_min}[k-1][i], \text{sparse\_min}[k-1][i + 2^{k-1}])\)$

これは「長さ \(2^k\) の区間」を「長さ \(2^{k-1}\) の区間2つ」に分けて考えています。

クエリへの回答

区間 \([l, r]\)（0-indexed）の長さを \(\text{len} = r - l + 1\) とし、\(k = \lfloor \log_2(\text{len}) \rfloor\) とします。

このとき、区間 \([l, l + 2^k - 1]\) と区間 \([r - 2^k + 1, r]\) の2つで元の区間を覆うことができます（一部重なっても問題ありません）。

区間 [l, r] の例（len=5, k=2）:
[l, l+3] と [r-3, r] で覆う
|-------|       ← 長さ4の区間
    |-------|   ← 長さ4の区間
|-----------|   ← 元の区間（長さ5）

最大値・最小値は冪等なので、重複部分があっても正しい結果が得られます。

計算量

• 時間計算量:
  • 前処理（Sparse Table構築）: \(O(N \log N)\)
  • 各クエリ: \(O(1)\)
  • 全体: \(O(N \log N + Q)\)
• 空間計算量: \(O(N \log N)\)（Sparse Tableの保持）

実装のポイント

1. 0-indexed への変換: 問題文は1-indexedなので、入力された \(L, R\) を l = L - 1, r = R - 1 と変換します。

2. 対数テーブルの事前計算: クエリごとに \(\log_2\) を計算すると遅くなるため、log_table[i] = \(\lfloor \log_2(i) \rfloor\) を事前に計算しておきます。

3. 出力の高速化: 結果を都度 print するのではなく、リストに溜めて最後にまとめて出力することで高速化しています。

4. N = 0 の場合の処理: エッジケースとして \(N = 0\) の場合を別途処理しています（今回の制約では不要ですが、安全のため）。

ソースコード

import sys
from math import log2, ceil

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sparse Table for range minimum and maximum queries
    if N == 0:
        for _ in range(Q):
            print(0)
        return
    
    K = max(1, ceil(log2(N + 1)))
    
    # sparse_min[k][i] = minimum in range [i, i + 2^k - 1]
    # sparse_max[k][i] = maximum in range [i, i + 2^k - 1]
    sparse_min = [[0] * N for _ in range(K + 1)]
    sparse_max = [[0] * N for _ in range(K + 1)]
    
    # Initialize for k = 0 (ranges of length 1)
    for i in range(N):
        sparse_min[0][i] = A[i]
        sparse_max[0][i] = A[i]
    
    # Build sparse table
    for k in range(1, K + 1):
        length = 1 << k
        for i in range(N - length + 1):
            sparse_min[k][i] = min(sparse_min[k-1][i], sparse_min[k-1][i + (1 << (k-1))])
            sparse_max[k][i] = max(sparse_max[k-1][i], sparse_max[k-1][i + (1 << (k-1))])
    
    # Precompute log values
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    
    # Answer queries
    results = []
    for _ in range(Q):
        L, R = map(int, input().split())
        # Convert to 0-indexed
        l = L - 1
        r = R - 1
        length = r - l + 1
        k = log_table[length]
        
        range_min = min(sparse_min[k][l], sparse_min[k][r - (1 << k) + 1])
        range_max = max(sparse_max[k][l], sparse_max[k][r - (1 << k) + 1])
        
        results.append(range_max - range_min)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。