Static Array Queries

A static array does not change between queries. Many problems ask for many range queries on the same fixed data; the right preprocessing turns each query into \(O(1)\) or \(O(\log n)\) time instead of scanning the range every time.

Range sum

Build a prefix sum array once in \(O(n)\). The sum on \([l, r]\) (inclusive) is pref[r + 1] - pref[l].

See Prefix Arrays for the full pattern and 2D rectangle sums.

Range minimum / maximum (RMQ)

If the array never changes, you can answer min or max on any interval in \(O(1)\) after \(O(n \log n)\) preprocessing with a sparse table.

Idea: st[j][i] = min over \([i, i + 2^j - 1]\). Transitions combine two halves. Query \([l, r]\) uses the largest power of two fitting inside the length.

#include <vector>
#include <algorithm>
using namespace std;

// min RMQ; for max, replace min with max
vector<int> buildLogTable(int n) {
    vector<int> lg(n + 1, 0);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    return lg;
}

vector<vector<int>> buildSparseTableMin(const vector<int>& a) {
    int n = (int)a.size();
    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    vector<vector<int>> st(LOG, vector<int>(n));
    for (int i = 0; i < n; i++) st[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    return st;
}

int rmqMin(const vector<vector<int>>& st, const vector<int>& lg, int l, int r) {
    int j = lg[r - l + 1];
    return min(st[j][l], st[j][r - (1 << j) + 1]);
}

// usage: auto lg = buildLogTable(n); auto st = buildSparseTableMin(a);
//        int v = rmqMin(st, lg, l, r);

For only sums, prefix arrays are simpler and use less memory than a sparse table.

When the array changes

If elements are updated between queries, a static prefix or sparse table must be rebuilt or replaced. Use a Segment Tree / BIT (or similar) for dynamic range queries.

Summary

Query type	Static array	Typical approach
Sum on \([l,r]\)	Yes	Prefix sums, \(O(1)\)
Min / max on \([l,r]\)	Yes	Sparse table, \(O(1)\) query
With point / range updates	No	Fenwick tree, segment tree, etc.