Range Maximum Query Using Sparse Table – Theory, Preprocessing, and C++ Implementation

The problem is to find the maximum value within any given interval of an array of N numbers, where a naive linear scan would take O(n) time per query.

Because the array does not change, one might consider precomputing results for all intervals, but that requires O(n²) time and space, which is impractical for large N.

The article introduces the sparse table technique, an offline preprocessing method that builds a table in O(n log n) time and answers each query in O(1) time. The table stores the maximum for intervals whose lengths are powers of two.

Define f[i][j] as the maximum value in the interval starting at index i with length 2^j. The recurrence relation is f[i][j] = max(f[i][j‑1], f[i + 2^{j‑1}][j‑1]), allowing the table to be filled by increasing j.

State compression is achieved by using the two dimensions (starting index i and exponent j) directly, reducing memory usage while preserving all needed information.

To answer a query for interval [a, b], compute j = ⌊log₂(b‑a+1)⌋. The answer is max(f[a][j], f[b‑2^j+1][j]), which combines two pre‑computed power‑of‑two intervals that together cover [a, b].

The article provides a complete C++ implementation. First, the arrays are declared: int high[50000][17], low[50000][17], n, q; Then the preprocessing function:

void solve()
{
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            high[i][j] = max(high[i][j-1], high[i + (1 << (j-1))][j-1]);
            low[i][j]  = min(low[i][j-1],  low[i + (1 << (j-1))][j-1]);
        }
    }
}

And the main function that reads input, builds the table, and processes queries:

int main()
{
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> high[i][0];
        low[i][0] = high[i][0];
    }
    solve();
    for (int i = 0; i < q; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        int j = (int)(log(b - a + 1.0) / log(2.0));
        int minHeight = min(low[a][j], low[b - (1 << j) + 1][j]);
        int maxHeight = max(high[a][j], high[b - (1 << j) + 1][j]);
        cout << maxHeight - minHeight << endl;
    }
    return 0;
}

In conclusion, the sparse table provides a highly efficient solution for static range maximum (or minimum) queries, leveraging preprocessing, state compression, and dynamic programming; for mutable data, a segment tree or other online structure would be required.