Efficient Static Range Maximum Query: An In-depth Analysis of Dynamic Programming and Doubling Algorithm

Core Logic and Mathematical Principles

Dynamic Programming and Doubling Space Power Set

The essence of the Sparse Table (ST) is a doubling algorithm based on the idea of dynamic programming, primarily used to solve the static range maximum query (RMQ) problem. Its mathematical foundation lies in the property of idempotent operations, which states that for any idempotent operator $f(x, x) = x$ (such as $\text{max}, \text{min}, \text{gcd}$), the results of operations on multiple overlapping subranges are equal to the results of operations on their union.

Let $f[i][j]$ denote the maximum value of the subrange of length $2^j$ in the range $[i, i + 2^j - 1]$. Using the doubling idea, the range of length $2^j$ is divided into two subranges of length $2^{j-1}$:

Left half range: $[i, i + 2^{j-1} - 1]$
Right half range: $[i + 2^{j-1}, i + 2^j - 1]$

The state transition equation is:

$$f[i][j] = \text{max}(f[i][j-1], f[i + 2^{j-1}][j-1])$$

$O(1)$ Complexity of Space Coverage

For any query range $[L, R]$, the length is $len = R - L + 1$. Let $k = \lfloor \text{log}_2(len) \rfloor$. Since $2^k \le len < 2^{k+1}$, the range $[L, R]$ can be completely covered by two subranges of length $2^k$, starting from $L$ and $R$, respectively:

$$[L, R] = [L, L + 2^k - 1] \bigcup [R - 2^k + 1, R]$$

Thus, the RMQ query degenerates into a constant-level algebraic mapping:

$$\text{RMQ}(L, R) = \text{max}(f[L][k], f[R - 2^k + 1][k])$$

State Design and Algorithm Derivation

Trade-off Between Space and Time

In the state definition, the first dimension $i$ maps to the sequence index, with a boundary of $N$; the second dimension $j$ maps to the powers of 2, with a boundary of $\lfloor \text{log}_2 N \rfloor$. In the preprocessing stage, the outer layer enumerates the power $j$, while the inner layer enumerates the index $i$. If the loop order is swapped incorrectly, it will lead to uncomputed states being referenced prematurely, disrupting the topological order of dynamic programming.

The preprocessing time complexity is:

$$\text{O}(N \text{ log } N)$$

In the query stage, the value of $k$ is calculated through bitwise operations or inline chip instructions (such as __builtin_clz), eliminating loop iterations to achieve $O(1)$ queries.

C++ Standard Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Encapsulate the ST table structure to avoid global variable naming pollution
struct SparseTable {
    int n;
    vector<int> log_table;
    vector<vector<int>> st;

    void init(const vector<int>& arr) {
        n = arr.size();
        int max_log = 0;
        while ((1 << max_log) <= n) max_log++;

        st.assign(n, vector<int>(max_log));
        log_table.assign(n + 1, 0);

        // Preprocess the log table, avoid calling std::log2() during queries to prevent floating-point overhead
        log_table[1] = 0;
        for (int i = 2; i <= n; i++) {
            log_table[i] = log_table[i >> 1] + 1;
        }

        // Fill the base states
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }

        // Critical pitfall: the outer layer must enumerate power $j$, and the inner layer enumerates index $i$, ensuring the topological order of DP state transitions
        for (int j = 1; j < max_log; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int l, int r) {
        // Convert input parameters to 0-indexed boundary control
        int len = r - l + 1;
        int k = log_table[len];
        // Critical pitfall: the starting point of the right half interval is r - (1 << k) + 1, bitwise operator precedence is low, parentheses are necessary
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

int main() {
    // Force synchronization of input and output streams to speed up IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    SparseTable table;
    table.init(arr);

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        // Convert to 0-indexed input
        cout << table.query(l - 1, r - 1) << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

Loop Order Reversal and Boundary Overflow
When preprocessing the ST table, some contestants habitually place $i$ in the outer layer and $j$ in the inner layer. Since $st[i][j]$ depends on $st[i + 2^{j-1}][j-1]$, when $i$ is in the outer layer, the state needed to compute the current state at $i + 2^{j-1}$ has not yet been scanned by the outer loop, leading to reading uninitialized garbage values. Furthermore, the inner control boundary i + (1 << j) - 1 < n may be missing, which can cause array out-of-bounds errors (SIGSEGV).
Bitwise Operator Precedence and Constant Disasters
In the query statement r - (1 << k) + 1, if written as r - 1 << k + 1, due to the precedence of addition and subtraction being higher than that of the shift operator, the actual execution logic becomes (r - 1) << (k + 1), leading to a complete collapse of the range logic. Another critical low-level error is the frequent calling of the library function std::log2() during the query or preprocessing stages, which involves floating-point calculations and FPU instruction conversions, resulting in high constant overhead, causing TLE at the level of $10^6$ queries. It is essential to use recursive arrays or built-in chip assembly instructions to compute $O(1)$ logarithms.

Classic NOIP/Luogu Problems

Luogu P3865 [Template] ST Table

Problem Description: Given a sequence of length $N$ and $M$ queries, each requiring the maximum value in the range $[L, R]$. $N, M \le 10^5$.
Nature of the Problem and Core Idea: A standard template for static range maximum queries. Any $O(\text{log } N)$ query solution using segment trees or binary indexed trees faces constant time risks under standard time limits for this problem. The essence of solving the problem is to preprocess all maximum values of length $2^j$ using the doubling method and achieve $O(1)$ responses through constant-level space overlapping.

Luogu P2880 [USACO07JAN] Balanced Lineup G

Problem Description: Given a sequence of cow heights each day, multiple queries ask for the height difference between the tallest and shortest cows within a specific range. $N \le 5 \times 10^4$, $M \le 2 \times 10^5$.
Nature of the Problem and Core Idea: A multi-metric static RMQ problem. The essence of the problem is to maintain both the maximum and minimum values within the range simultaneously. Since static does not involve modification operations, it is sufficient to establish two independent ST tables to maintain $\text{max}$ and $\text{min}$. During queries, the results from both tables can be read in $O(1)$ and then subtracted to obtain the difference.