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

Core Logic and Mathematical Principles

1. Problem Background

Given a fixed sequence of length $N$, perform $M$ range maximum queries (RMQ):

• Naive approach: traverse the interval $[L, R]$ for each query, resulting in $O(N)$ time per query and $O(M \times N)$ total time, which will time out completely when facing large-scale data.
• ST table solution: preprocess the log array in $O(N)$, build the $f$ table in $O(N \log N)$, and achieve $O(1)$ per query, optimizing the total time complexity to $O(N \log N) + M$.

2. Idempotence and Repeatable Contribution

The essence of the ST table (Sparse Table) is a doubling algorithm based on dynamic programming, used to solve static range maximum/minimum queries.

Its mathematical foundation lies in the property of repeatable contribution (Idempotent Operations), which states that for any binary idempotent operator $*$ satisfying $x * x = x$ (such as $\max, \min, \gcd$, and bitwise operations $\&, |$), the result of operations on multiple overlapping subintervals equals the result of operations on their union.

Concept Breakdown: "Idempotent" comes from "idem" (same) and "potent" (power). Literally, it means "the result of a higher power is the same as the first power." The core idea is: performing an operation once versus performing it any number of times yields exactly the same final result.

3. Constant-Level Space Coverage

For any query interval $[L, R]$, its length is $len = R - L + 1$. Let $k = \lfloor \log_2(len) \rfloor$.

Since $2^k \le len < 2^{k+1}$, the interval $[L, R]$ can be completely covered by two subintervals of length $2^k$, one starting at $L$ and the other ending at $R$ (overlap in the middle is allowed). The set relationship is expressed as:

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

Based on idempotence, the overlapping portion does not affect the final maximum/minimum result. Thus, the entire RMQ query is reduced to a constant-level algebraic mapping, directly achieving $O(1)$ query:

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

State Design and Algorithm Derivation

1. State Definition and Doubling Recurrence

In the state definition:

• The first dimension $i$ maps to the sequence index, with a boundary of $N$.
• The second dimension $j$ maps to powers of $2$, with a boundary of $\lfloor \log_2 N \rfloor$.

Let $f[i][j]$ denote the maximum value of the subinterval of length $2^j$ in the range $[i, i + 2^j - 1]$. Using the doubling idea, the current state (a large interval of length $2^j$) is recursively merged (doubled) from two subintervals of length $2^{j-1}$ from the previous layer $j-1$:

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

The state transition equation is:

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

2. Topological Order and Loop Sequence

When writing the preprocessing code, the outer loop must enumerate the power $j$, and the inner loop must enumerate the index $i$.

Computing the large interval state of the current layer $j$ must depend on the already computed small interval state of the previous layer $j-1$.

3. Constant-Level Optimization of the $\log$ Array

To truly achieve $O(1)$ speed during the query phase, loop iterations must be eliminated, and direct calls to the expensive and precision-prone std::log2() math library function must be avoided.

The recommended approach is to precompute the floor of $\log_2$ for all possible intervals from $1$ to $N$ through linear-time $O(N)$ recursion during the preprocessing phase. The query then simply looks up the table:

// Preprocess log array
lg[1] = 0;
for (int i = 2; i <= n; i++) {
    lg[i] = lg[i >> 1] + 1;
}

Through the above optimization, the query only needs to execute int k = lg[len];, perfectly guaranteeing constant-level response.

const int MAXN = 100005; // Adjust according to problem constraints
const int MAXJ = 21;     // log2(MAXN) + 2

int n;
int a[MAXN];
int lg[MAXN];
int st[MAXN][MAXJ];

// ST table preprocessing: O(N log N)
void init() {
    // 1. Linear recursion to preprocess log array
    lg[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    // 2. Inject DP initial states (1-indexed)
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }

    // 3. Core doubling DP: outer loop enumerates powers, inner loop enumerates indices
    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// O(1) range maximum query
inline int query(int l, int r) {
    int len = r - l + 1;
    int k = lg[len];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

NOIP Practical Pitfall Guide

1. Loop Order Reversal and Boundary Overflow

   • Loop Order Reversal: During preprocessing, the outer loop must enumerate the power $j$, and the inner loop must enumerate the index $i$. Since the state transition st[i][j] strongly depends on st[i + (1 << (j - 1))][j - 1] from the previous layer, if $i$ is in the outer loop, the small interval state at a larger index required for computing the current state has not yet been scanned, directly breaking the topological order of DP and causing the algorithm to read uninitialized garbage values.
   • Boundary Overflow: Under the 1-indexed system, the inner loop condition must be strictly limited to i + (1 << j) - 1 <= n. Missing boundary control or incorrectly writing < n will cause out-of-bounds array access, easily triggering a segmentation fault (SIGSEGV) or causing inexplicable memory corruption on the judging system.

2. Bitwise Operator Precedence and Constant Disasters

   • Precedence Pitfall: In interval coverage queries, the starting point of the right half interval is r - (1 << k) + 1. Since the precedence of addition/subtraction operators is higher than that of shift operators, if parentheses are omitted and written as r - 1 << k + 1, the actual execution logic becomes (r - 1) << (k + 1), causing the query range to be completely distorted. In any mixed expression involving bitwise operations, always add sufficient parentheses.
   • Constant Disaster: It is strictly prohibited to frequently call the std::log2() function from the <cmath> library during preprocessing or querying. This function is designed for floating-point numbers, involving FPU floating-point instruction conversions with potential precision risks. Its significant constant overhead under high-frequency queries at the $10^6$ level will directly undermine the theoretical $O(1)$ advantage, causing TLE. Use $O(N)$ linear array recursion to precompute a table, achieving pure integer constant-level table lookup.

Classic NOIP/Luogu Problems

Luogu P3865 [Template] ST Table

• Problem Description: Given a sequence of length $N$ and $M$ queries, each query asks for the maximum value in the interval $[L, R]$. Constraints: $N \le 10^5$, $M \le 2 \times 10^6$.
• Problem Essence and Core Solution: A standard template for static range maximum queries. Any $O(M \log N)$ solution using segment trees or Fenwick trees faces serious TLE risks under the extremely large number of queries ($2 \times 10^6$) in this problem. The essence of the solution is to preprocess all maximum values of intervals of length $2^j$ using the doubling method, leveraging idempotence to achieve $O(1)$ responses through constant-level spatial overlap coverage.

Core Algorithm Code

// P3865 Core Code: Single-metric maximum ST table
int lg[MAXN], st[MAXN][MAXJ];

void init(int n, int a[]) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) st[i][0] = a[i];

    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

inline int query(int l, int r) {
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

Luogu P2880 [USACO07JAN] Balanced Lineup G

• Problem Description: Given a sequence of daily cow heights, multiple queries ask for the height difference between the tallest and shortest cows in a specific interval. Constraints: $N \le 5 \times 10^4$, $M \le 2 \times 10^5$.
• Problem Essence and Core Solution: A multi-metric static RMQ problem. The essence is to simultaneously maintain both the maximum and minimum values in the interval. Since the data is static and does not involve modifications, simply build two independent ST tables to maintain $\max$ and $\min$ respectively. During queries, read the results from both tables in $O(1)$ and compute the difference.

Core Algorithm Code

// P2880 Core Code: Dual-metric max/min ST table
int lg[MAXN];
int st_max[MAXN][MAXJ], st_min[MAXN][MAXJ];

void init(int n, int a[]) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) st_max[i][0] = st_min[i][0] = a[i];

    for (int j = 1; j <= lg[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
            st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
        }
    }
}

inline int query_diff(int l, int r) {
    int k = lg[r - l + 1];
    int mx = max(st_max[l][k], st_max[r - (1 << k) + 1][k]);
    int mn = min(st_min[l][k], st_min[r - (1 << k) + 1][k]);
    return mx - mn;
}