Sparse Table

A sparse table answers queries on an array that does not change. It precomputes answers for every valid interval whose length is a power of two. For minimum and maximum, a query can combine two possibly overlapping blocks in constant time because repeating values does not change the result. This property is called idempotence. Sparse tables are an excellent choice when there are many range-minimum queries and no updates. They trade more preprocessing memory for exceptionally simple and fast queries.

Prerequisites: Arrays, powers of two, range minima, associative operations.

Build the idea

1. Build power-of-two blocks

   Let st[k][i] be the minimum of the 2^k values starting at i. The base row st[0][i] is a[i]. A longer block splits into two adjacent halves: st[k][i]=min(st[k-1][i],st[k-1][i+2^(k-1)]). Both halves were built in the previous row. Build only entries whose full interval lies inside the array; unbuilt cells must never be queried.

2. Cover a query with two blocks

   For [l,r] of length len, take k=floor(log2(len)). Use blocks [l,l+2^k-1] and [r-2^k+1,r]. Since 2^k≤len<2^(k+1), the blocks fit inside the query and together cover it. They may overlap; min(x,x)=x makes duplicate coverage harmless. Therefore the query is min(st[k][l],st[k][r-2^k+1]).

3. Work a query by hand

   For [7,2,6,3,9,1], query [2,5] has length 4, so k=2. Both chosen blocks are [2,5] and the answer is 2. Query [2,6] has length 5: combine [2,5] with [3,6], returning min(2,1)=1. Positions 3–5 appear twice, but the minimum remains correct. A single-element interval uses row zero.

4. Why sum is different

   The overlapping trick is invalid for sum because x+x usually differs from x. You can answer associative sum queries by decomposing into disjoint power-of-two blocks in O(log n), but static prefix sums are simpler and use less memory. Greatest common divisor, bitwise AND, and bitwise OR are idempotent and support the two-block pattern. The operation must also be associative.

5. Logarithms and updates

   Precompute lg[len]=lg[len/2]+1 to obtain floor(log2(len)) exactly without floating-point rounding. The program stores levels as rows and keeps original positions 1-based. Changing one array value can invalidate many table entries, so this implementation has no update command. If updates are needed, prefer a segment tree rather than pretending the precomputed table stays valid.

6. A coverage proof you can reuse

   Let b=2^k be the selected block length. The left block ends at l+b-1 and the right block starts at r-b+1. A gap would require l+b-1<r-b, equivalent to 2b<r-l+1. But the chosen floor logarithm guarantees len<2b, so a gap cannot occur. Both blocks also stay inside the query because b≤len. Coverage and idempotence together prove the answer.

   Consider a large static dataset with millions of queries. A segment tree would reduce preprocessing memory to linear but require a logarithmic traversal per query. A sparse table instead pays for multiple levels once and performs constant-time queries. Neither is universally better: compare the available memory, whether data changes, the operation's algebraic properties, and the number of queries. For n=1 there is just one level; the formula selects the same single cell twice, correctly returning its value.

7. As a manual check, build the length-two row first, then the length-four row. Compare a full-array query and a single-element query against a direct scan before trusting larger tests.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<long long>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // Exact integer floor logarithms avoid floating-point rounding.
    vector<int>lg(n+1,0);
    for(int len=2;len<=n;len++){
        lg[len]=lg[len/2]+1;
    }
    int levels=lg[n]+1;
    vector<vector<long long>>st(levels,vector<long long>(n+1));
    for(int i=1;i<=n;i++){
        st[0][i]=a[i];
    }
    // A length-2^k block combines two adjacent length-2^(k-1) blocks.
    for(int k=1;k<levels;k++){
        int half=1<<(k-1),length=1<<k;
        // Build only complete blocks that fit inside the original array.
        for(int i=1;i+length-1<=n;i++){
            st[k][i]=min(st[k-1][i],st[k-1][i+half]);
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        int k=lg[r-l+1];
        // Overlap is safe because minimum is idempotent.
        cout<<min(st[k][l],st[k][r-(1<<k)+1])<<'\n';
    }
}

Complexity analysis

Preprocessing O(n log n) time and memory. Each static minimum query O(1): two table accesses and one minimum. The logarithm table uses O(n) extra space. No efficient updates are provided.

Example input and output

n q; n immutable values; q inclusive ranges l r, with n≥1 and 1≤l≤r≤n.

Input

6 3
7 2 6 3 9 1
2 5
2 6
4 4

Output

2
1
3

The minima of positions 2–5, 2–6, and the single position 4 are 2, 1, and 3.

Practical applications

Static range minima/maxima; gcd queries; LCA via an Euler walk and minimum-depth queries; repeated interval checks on immutable data.

Check your understanding

Why can the two blocks overlap in a minimum query?

Put it into practice

Change the operation to gcd and explain why overlapping coverage remains valid.