Range Minimum/Maximum Query (RMQ) algorithms efficiently compute the minimum and maximum values across multiple subarrays within a sequence. These algorithms preprocess the data to enable constant-time queries, making them suitable for applications requiring repeated range queries on static data.

Given a sequence of N elements, RMQ preprocessing constructs data structures that allow O(1) retrieval of minimum and maximum values for any subarray [L, R]. This approach significantly outperforms naive O(N) per-query solutions when handling numerous queries.

Sparse Table Implementation

The sparse table technique uses dynamic programming to precompute range results for all possible power-of-two lengths. Two 2D arrays store maximum and minimum values:

• max_table[i][k]: Maximum value in range [i, i + 2^k - 1]
• min_table[i][k]: Minimum value in range [i, i + 2^k - 1]

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 50010;
const int LOG_MAX = 17;

int arr[MAX_N];
int max_table[MAX_N][LOG_MAX];
int min_table[MAX_N][LOG_MAX];

void build_sparse_table(int n) {
    for (int i = 1; i <= n; i++) {
        max_table[i][0] = arr[i];
        min_table[i][0] = arr[i];
    }
    
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            max_table[i][j] = max(max_table[i][j-1], max_table[i + (1 << (j-1))][j-1]);
            min_table[i][j] = min(min_table[i][j-1], min_table[i + (1 << (j-1))][j-1]);
        }
    }
}

int range_query(int left, int right) {
    int span = right - left + 1;
    int exponent = log2(span);
    
    int max_val = max(max_table[left][exponent], max_table[right - (1 << exponent) + 1][exponent]);
    int min_val = min(min_table[left][exponent], min_table[right - (1 << exponent) + 1][exponent]);
    
    return max_val - min_val;
}

int main() {
    int num_elements, num_queries;
    cin >> num_elements >> num_queries;
    
    for (int i = 1; i <= num_elements; i++) {
        cin >> arr[i];
    }
    
    build_sparse_table(num_elements);
    
    while (num_queries--) {
        int start, end;
        cin >> start >> end;
        cout << range_query(start, end) << endl;
    }
    
    return 0;
}

Algorithm Analysis

• Preprocessing Time: O(N log N)
• Query Time: O(1)
• Space Complexity: O(N log N)

The preprocessing phase computes values for all segments with lengths that are powers of two. Each query then combines two overlapping segments that cover the entire range, ensuring complete coverage while maintaining constant-time performance.