Sparse Tables and RMQ

Static range minimum/maximum queries, idempotent operations, overlapping intervals, logarithm lookup, disjoint sparse tables for broader associative operations, and comparison with segment trees.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Build O(n log n), query O(1). The two blocks of length 2ᵏ overlap, which is harmless for idempotent operations (min, max, gcd, bitwise and/or) but would double-count for sums. A disjoint sparse table splits at a midpoint per level so blocks never overlap, giving O(1) queries for any associative operation. A segment tree takes O(log n) per query but supports updates.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {7, 2, 9, 4, 8, 1, 6, 3, 5};
    int n = (int)a.size(), K = 32 - __builtin_clz(n);
    vector<vector<int>> sp(K, vector<int>(n));
    sp[0] = a;
    for (int k = 1; k < K; ++k)                                            // sp[k][i] = min of a[i .. i + 2^k)
        for (int i = 0; i + (1 << k) <= n; ++i) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
    auto rmq = [&](int l, int r) {                                         // [l, r], two overlapping blocks
        int k = 31 - __builtin_clz(r - l + 1);
        return min(sp[k][l], sp[k][r - (1 << k) + 1]);
    };
    cout << "min of a[2..6] = " << rmq(2, 6) << ", min of a[0..3] = " << rmq(0, 3) << ", min of a[6..8] = " << rmq(6, 8) << '\n';
    for (int l = 0; l < n; ++l) for (int r = l; r < n; ++r)
        if (rmq(l, r) != *min_element(a.begin() + l, a.begin() + r + 1)) { cout << "mismatch\n"; return 1; }
    cout << "all " << n * (n + 1) / 2 << " ranges match a direct scan; table uses " << K << " levels\n";
}

min of a[2..6] = 1, min of a[0..3] = 2, min of a[6..8] = 3
all 45 ranges match a direct scan; table uses 4 levels

Quiz

? Why can a sparse table answer range-sum queries with two overlapping blocks only incorrectly?
+ The overlap would be counted twice; sum is not idempotent. :: Min, max and gcd are fine.
- Sums overflow. :: Not the reason.
- Sparse tables cannot store sums. :: They can store them; the overlap query is the problem.
- It works fine. :: It double-counts.

? Build and query costs of a sparse table?
+ O(n log n) build, O(1) query :: Static data only.
- O(n) build, O(log n) query :: That is a segment tree.
- O(1) build :: No.
- O(n²) build :: That is the naive all-pairs table.

? Which operations can use the overlapping two-block query? (select all that apply)
+ min :: Idempotent.
+ gcd :: Idempotent.
- sum :: Not idempotent.
+ bitwise OR :: Idempotent.