Overview

This problem asks us to quickly compute the difference between the maximum and minimum values within a specified interval \([L, R]\) for multiple queries. By using a Sparse Table, we can answer each query in \(O(1)\).

Analysis

Naive Approach and Its Issues

The simplest method is to iterate through the interval \([L, R]\) for each query to find the maximum and minimum values.

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

This method takes \(O(N)\) per query, resulting in \(O(NQ)\) overall. Under the constraints \(N, Q \leq 10^5\), this leads to up to \(10^{10}\) operations, causing TLE (Time Limit Exceeded).

Solution Strategy

“Finding the maximum/minimum value in an interval quickly” is a classic problem known as Range Minimum/Maximum Query (RMQ).

A key observation is that maximum and minimum operations have idempotence (the property that seeing the same element twice doesn’t change the result). For example, \(\max(3, 3) = 3\). Leveraging this property, we can use a Sparse Table to solve the problem with \(O(N \log N)\) preprocessing and \(O(1)\) per query.

Algorithm

Sparse Table Construction

A Sparse Table is a data structure that precomputes information about “intervals whose lengths are powers of \(2\)”.

• \(\text{sparse\_min}[k][i]\) = minimum value in the interval of length \(2^k\) starting at position \(i\)
• \(\text{sparse\_max}[k][i]\) = maximum value in the interval of length \(2^k\) starting at position \(i\)

Recurrence relation for construction: $\(\text{sparse\_min}[k][i] = \min(\text{sparse\_min}[k-1][i], \text{sparse\_min}[k-1][i + 2^{k-1}])\)$

This divides “an interval of length \(2^k\)” into “two intervals of length \(2^{k-1}\)”.

Answering Queries

Let the length of interval \([l, r]\) (0-indexed) be \(\text{len} = r - l + 1\), and let \(k = \lfloor \log_2(\text{len}) \rfloor\).

Then, the two intervals \([l, l + 2^k - 1]\) and \([r - 2^k + 1, r]\) can cover the original interval (overlapping is not a problem).

Example of interval [l, r] (len=5, k=2):
Cover with [l, l+3] and [r-3, r]
|-------|       ← interval of length 4
    |-------|   ← interval of length 4
|-----------|   ← original interval (length 5)

Since maximum and minimum are idempotent, we get the correct result even with overlapping parts.

Complexity

• Time Complexity:
  • Preprocessing (Sparse Table construction): \(O(N \log N)\)
  • Each query: \(O(1)\)
  • Overall: \(O(N \log N + Q)\)
• Space Complexity: \(O(N \log N)\) (for storing the Sparse Table)

Implementation Notes

1. Conversion to 0-indexed: Since the problem uses 1-indexed values, convert the input \(L, R\) to l = L - 1, r = R - 1.

2. Precomputing the logarithm table: Computing \(\log_2\) for each query is slow, so precompute log_table[i] = \(\lfloor \log_2(i) \rfloor\).

3. Output optimization: Instead of calling print for each result, collect results in a list and output them all at once at the end for faster execution.

4. Handling the case N = 0: As an edge case, handle \(N = 0\) separately (not required under the given constraints, but included for safety).

   Source Code

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

---

This editorial was generated by claude4.5opus.