SyntaxPilot
Courses/Competitive Programming/Lesson 64
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 64 of 90

Sparse table and RMQ on contests

queued

These are the notes for Competitive Programming episode 64. A sparse table stores mn[j][i], the minimum of the 2^j values starting at i, for every i and every j: O(n log n) numbers built from two halves each. A query [l, r] takes k = ⌊log₂(r − l + 1)⌋ and returns min(mn[k][l], mn[k][r − 2^k + 1]): two overlapping stretches that cover [l, r]. Overlap is harmless for idempotent operations (min, max, gcd, AND, OR), so every query is O(1); for sums the overlap counts the middle twice. Low Bridges (lowest bridge and total toll on a trip) shows the loop (TLE), the sparse table, and the overlap bug for tolls (16 instead of 11), fixed with prefix sums. Calm Stretches counts stretches with max − min ≤ K: from every start is TLE, two pointers with O(1) range max/min is accepted. Range gcd works with the same trick. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A transport office keeps a chart: for every starting bridge, the lowest bridge among the next 1, 2, 4, 8, … bridges. A trip over 6 bridges is covered by "the first 4" and "the last 4", which overlap in the middle; the lowest bridge of the trip is the lower of the two chart entries. Seeing a bridge twice doesn't change the lowest one. But adding up tolls that way would make the middle bridges pay twice.

Problem L1 · Low Bridges

(Written for this course, in the style of a classic RMQ problem.)

  • Input: n q (n, q ≤ 5 · 10^5), heights h[1..n], tolls c[1..n], then q trips l r.
  • Output per trip: min(h[l..r]) and c[l] + … + c[r].
6 4
7 3 9 4 8 5
2 1 3 2 2 1
1 6
3 6
5 5
1 3

Answers: 3 11, 4 8, 8 2, 3 6.

The obvious attempt: loop per truck (TLE)

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

int n, q, h[500001];
ll c[500001];

int lowest(int l, int r) {
    int m = INT_MAX;
    for (int i = l; i <= r; i++) m = min(m, h[i]);
    return m;
}
ll toll(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) s += c[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << lowest(l, r) << " " << toll(l, r) << "\n";
    }
}
3 11
4 8
8 2
3 6
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, h[500001];
ll c[500001];

int lowest(int l, int r) {
    int m = INT_MAX;
    for (int i = l; i <= r; i++) m = min(m, h[i]);
    return m;
}
ll toll(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) s += c[i];
    return s;
}

int main() {
    n = q = 500000;                          // half a million bridges and trucks
    mt19937 rng(64);
    for (int i = 1; i <= n; i++) h[i] = rng() % 1000000000 + 1, c[i] = rng() % 100;
    ll check = 0;
    for (int i = 0; i < q; i++) {
        int l = rng() % 10 + 1, r = n - rng() % 10;   // long trips
        check ^= lowest(l, r) + toll(l, r);
    }
    cout << check << "\n";
}
Time Limit Exceeded

The sparse table

  • mn[0][i] = h[i]; mn[j][i] = min(mn[j−1][i], mn[j−1][i + 2^(j−1)]), for every i with i + 2^j − 1 ≤ n.
  • Query: k = __lg(r − l + 1) (the highest set bit, an exact integer); answer min(mn[k][l], mn[k][r − 2^k + 1]). Since 2^k ≤ len < 2^(k+1), the two stretches cover [l, r] and stay inside it.
  • LOG with 2^LOG > n; storing mn[LOG][n] (level first) keeps memory access in order.

On the sample, trip [1, 6]: len 6, k = 2, stretches [1, 4] (min 3) and [3, 6] (min 4): answer 3.

Idempotent operations

An operation ⊕ is idempotent if x ⊕ x = x. Then covering some elements twice doesn't change the result: min, max, gcd, bitwise AND/OR. Sum, product and xor are not idempotent: their range queries need prefix sums (or a disjoint decomposition, e.g. a Fenwick tree or a disjoint sparse table).

The bug: the same trick for the tolls

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

int n, q, h[500001];
ll c[500001];
const int LOG = 19;                            // 2^19 > 5·10^5
int mn[LOG][500001];                           // mn[j][i] = lowest of h[i .. i + 2^j − 1]
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = h[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);   // two halves
}
int lowest(int l, int r) {                     // two overlapping stretches
    int k = __lg(r - l + 1);
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
ll sm[LOG][500001];                            // the same trick for tolls?
void buildSum() {
    for (int i = 1; i <= n; i++) sm[0][i] = c[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            sm[j][i] = sm[j - 1][i] + sm[j - 1][i + (1 << (j - 1))];
}
ll toll(int l, int r) {
    int k = __lg(r - l + 1);
    return sm[k][l] + sm[k][r - (1 << k) + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    build();
    buildSum();
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << lowest(l, r) << " " << toll(l, r) << "\n";
    }
}
3 16
4 16
8 4
3 7

The heights are right; every toll counts the overlap twice (a single bridge even pays double). With prefix sums:

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

int n, q, h[500001];
ll c[500001];
const int LOG = 19;                            // 2^19 > 5·10^5
int mn[LOG][500001];                           // mn[j][i] = lowest of h[i .. i + 2^j − 1]
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = h[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);   // two halves
}
int lowest(int l, int r) {                     // two overlapping stretches
    int k = __lg(r - l + 1);
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
ll pre[500001];                                // tolls: prefix sums, no overlap
void buildSum() { for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i]; }
ll toll(int l, int r) { return pre[r] - pre[l - 1]; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    build();
    buildSum();
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << lowest(l, r) << " " << toll(l, r) << "\n";
    }
}
3 11
4 8
8 2
3 6
10 4
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q, h[500001];
ll c[500001];
const int LOG = 19;                            // 2^19 > 5·10^5
int mn[LOG][500001];                           // mn[j][i] = lowest of h[i .. i + 2^j − 1]
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = h[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);   // two halves
}
int lowest(int l, int r) {                     // two overlapping stretches
    int k = __lg(r - l + 1);
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
ll pre[500001];                                // tolls: prefix sums, no overlap
void buildSum() { for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i]; }
ll toll(int l, int r) { return pre[r] - pre[l - 1]; }

int main() {
    n = q = 500000;                          // half a million bridges and trucks
    mt19937 rng(64);
    for (int i = 1; i <= n; i++) h[i] = rng() % 1000000000 + 1, c[i] = rng() % 100;
    build();
    buildSum();
    ll check = 0;
    for (int i = 0; i < q; i++) {
        int l = rng() % 10 + 1, r = n - rng() % 10;   // long trips
        check ^= lowest(l, r) + toll(l, r);
    }
    cout << check << "\n";
}
918

Stress test

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

int n, q, h[500001];
ll c[500001];
const int LOG = 19;                            // 2^19 > 5·10^5
int mn[LOG][500001];                           // mn[j][i] = lowest of h[i .. i + 2^j − 1]
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = h[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);   // two halves
}
int lowest(int l, int r) {                     // two overlapping stretches
    int k = __lg(r - l + 1);
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
int main() {
    mt19937 rng(64);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 40 + 1;
        for (int i = 1; i <= n; i++) h[i] = rng() % 100;
        build();
        for (int k = 0; k < 50; k++) {
            int l = rng() % n + 1, r = rng() % n + 1;
            if (l > r) swap(l, r);
            if (lowest(l, r) != *min_element(h + l, h + r + 1)) { cout << "mismatch on test " << t; return 0; }
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Range gcd with the same trick

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

const int LOG = 19;
int n, q, a[500001], g[LOG][500001];      // g[j][i] = gcd of a[i .. i + 2^j − 1]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], g[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            g[j][i] = __gcd(g[j - 1][i], g[j - 1][i + (1 << (j - 1))]);
    while (q--) {
        int l, r;
        cin >> l >> r;
        int k = __lg(r - l + 1);
        cout << __gcd(g[k][l], g[k][r - (1 << k) + 1]) << "\n";   // overlap is fine
    }
}
6 3
12 18 24 30 6 9
1 4
2 5
4 6
6
6
3

Problem L2 · Calm Stretches

(Written for this course.)

  • Input: n K (n ≤ 5 · 10^5), readings a[1..n]. A stretch [l, r] is calm if max − min ≤ K. Count the calm stretches (long long: up to n(n + 1) / 2).
7 2
1 3 2 6 4 4 9

Answer: 13.

Observation. A calm stretch stays calm when it shrinks. So for each right end r, the calm starts form a suffix l..r, and the smallest good l never moves left as r grows: two pointers. Each check needs max − min of [l, r] in O(1): two sparse tables.

The obvious attempt: grow from every start (TLE)

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

int n, K, a[500001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll calm = 0;
    for (int l = 1; l <= n; l++) {                 // every start, grow to the right
        int lo = a[l], hi = a[l];
        for (int r = l; r <= n; r++) {
            lo = min(lo, a[r]), hi = max(hi, a[r]);
            if (hi - lo > K) break;
            calm++;
        }
    }
    cout << calm << "\n";
}
13

With readings 0..100 and K = 100 every stretch is calm, so every start grows to the end:

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

int n, K, a[500001];

int main() {
    n = 500000, K = 100;                      // readings 0..100: every stretch is calm
    mt19937 rng(64);
    for (int i = 1; i <= n; i++) a[i] = rng() % 101;
    ll calm = 0;
    for (int l = 1; l <= n; l++) {                 // every start, grow to the right
        int lo = a[l], hi = a[l];
        for (int r = l; r <= n; r++) {
            lo = min(lo, a[r]), hi = max(hi, a[r]);
            if (hi - lo > K) break;
            calm++;
        }
    }
    cout << calm << "\n";
}
Time Limit Exceeded

Two pointers + O(1) spread

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

int n, K, a[500001];
const int LOG = 19;
int mn[LOG][500001], mx[LOG][500001];
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = mx[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
        }
}
int spread(int l, int r) {                     // max − min of a[l..r] in O(1)
    int k = __lg(r - l + 1), s = r - (1 << k) + 1;
    return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build();
    ll calm = 0;
    int l = 1;
    for (int r = 1; r <= n; r++) {                 // two pointers
        while (spread(l, r) > K) l++;            // too wild: move the start
        calm += r - l + 1;                       // every start l..r works
    }
    cout << calm << "\n";
}
13
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, a[500001];
const int LOG = 19;
int mn[LOG][500001], mx[LOG][500001];
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = mx[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
        }
}
int spread(int l, int r) {                     // max − min of a[l..r] in O(1)
    int k = __lg(r - l + 1), s = r - (1 << k) + 1;
    return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s]);
}

int main() {
    n = 500000, K = 100;                      // readings 0..100: every stretch is calm
    mt19937 rng(64);
    for (int i = 1; i <= n; i++) a[i] = rng() % 101;
    build();
    ll calm = 0;
    int l = 1;
    for (int r = 1; r <= n; r++) {                 // two pointers
        while (spread(l, r) > K) l++;            // too wild: move the start
        calm += r - l + 1;                       // every start l..r works
    }
    cout << calm << "\n";
}
125000250000

(n = 5 · 10^5 gives n(n + 1) / 2 = 125,000,250,000 stretches.)

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

int n, K, a[500001];
const int LOG = 19;
int mn[LOG][500001], mx[LOG][500001];
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = mx[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
        }
}
int spread(int l, int r) {                     // max − min of a[l..r] in O(1)
    int k = __lg(r - l + 1), s = r - (1 << k) + 1;
    return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s]);
}

int main() {
    mt19937 rng(64);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 30 + 1, K = rng() % 6;
        for (int i = 1; i <= n; i++) a[i] = rng() % 10;
        build();
        ll fast = 0, slow = 0;
        int l = 1;
        for (int r = 1; r <= n; r++) {
            while (spread(l, r) > K) l++;
            fast += r - l + 1;
        }
        for (int x = 1; x <= n; x++)
            for (int y = x; y <= n; y++)
                slow += *max_element(a + x, a + y + 1) - *min_element(a + x, a + y + 1) <= K;
        if (fast != slow) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Build Query Verdict
L1: loop — O(n) TLE
segment tree O(n) O(log n), with updates accepted
sparse table O(n log n) time and memory (≈ 10^7 ints) O(1), static only accepted
L2: every start — O(n²) TLE
L2: two pointers + sparse tables O(n log n) O(n) total accepted

Each pointer in L2 moves at most n times, so there are at most 2n spread checks.

Where sparse tables show up

  • LCA: in an Euler tour of a tree, the LCA of u and v is the shallowest node between their first occurrences (homework 3).
  • Strings: the longest common prefix of two suffixes is a range minimum over the LCP array (episode 77).
  • Binary search that needs a range max/min at each step.
  • Window problems with max − min, gcd or AND, combined with two pointers.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
loop per query Time Limit Exceeded O(n · q) sparse table
overlap trick for sums 16 16 4 7 (expected 11 8 2 6) the middle counted twice prefix sums
floor(log2(len)) with doubles rare wrong k rounding __lg(len)
LOG too small out of bounds / WA level k doesn't exist 2^LOG > n
building past the end (i ≤ n instead of i + 2^j − 1 ≤ n) reads garbage stretch doesn't fit check the bound
using a sparse table with updates Time Limit Exceeded rebuild is O(n log n) segment tree
int count of stretches overflow up to 1.25 · 10^11 long long

Mini project

Write a SparseTable<T, Op> template (Op must be idempotent) with build(vector<T>) and query(l, r), and an argmin version that returns positions (homework 2). Use it for range min, range max, range gcd and LCA (homework 3); stress-test each against brute force, including n = 1 and lengths that are exact powers of two.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17); the LCA solution was also checked against a naive LCA on 100 random trees.

1. Range gcd queries.

Solution

gcd is idempotent, so the same table works with __gcd instead of min — exactly the GCD program above.

2. The position of the minimum (the leftmost one on ties).

Solution

Store positions instead of values and compare h[a] <= h[b] (keeping the left one on ties). Sample 7 3 9 3 8 5: [1, 6] → 2, [3, 6] → 4, [5, 6] → 6.

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

const int LOG = 19;
int n, q, h[500001], id[LOG][500001];      // id[j][i] = position of the lowest in h[i .. i + 2^j − 1]

int better(int a, int b) { return h[a] <= h[b] ? a : b; }   // ties: the leftmost (a < b in our calls)

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i], id[0][i] = i;
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            id[j][i] = better(id[j - 1][i], id[j - 1][i + (1 << (j - 1))]);
    while (q--) {
        int l, r;
        cin >> l >> r;
        int k = __lg(r - l + 1);
        cout << better(id[k][l], id[k][r - (1 << k) + 1]) << "\n";
    }
}
2
4
6

3. LCA with an Euler tour + RMQ.

Solution

Write down a node every time the DFS arrives at it or returns to it (2n − 1 entries). The LCA of u and v is the shallowest node between first[u] and first[v]: a range minimum over depths. O(n log n) build, O(1) per query.

7 4
1 2
1 3
2 4
2 5
3 6
5 7
4 7
6 7
2 5
3 3
#include <bits/stdc++.h>
using namespace std;

// LCA with an Euler tour + sparse table over depths.
const int N = 200005, LOG = 20;
vector<int> g[N];
int n, q, depth[N], first[N], euler[2 * N], len = 0, sp[LOG][2 * N];

int shallower(int a, int b) { return depth[a] < depth[b] ? a : b; }

int main() {
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b), g[b].push_back(a);
    }
    // iterative DFS from 1, writing a node every time we arrive at it or come back to it
    vector<pair<int, int>> st = {{1, 0}};
    vector<int> par(n + 1, 0), it(n + 1, 0);
    depth[1] = 0;
    while (!st.empty()) {
        int v = st.back().first;
        if (it[v] == 0) first[v] = len;
        euler[len++] = v;
        if (it[v] < (int)g[v].size()) {
            int u = g[v][it[v]++];
            if (u == par[v]) { len--; continue; }      // skip the parent, don't write v twice
            par[u] = v, depth[u] = depth[v] + 1;
            st.push_back({u, 0});
        } else st.pop_back();
    }
    for (int i = 0; i < len; i++) sp[0][i] = euler[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 0; i + (1 << j) <= len; i++)
            sp[j][i] = shallower(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
    while (q--) {
        int a, b;
        cin >> a >> b;
        int l = min(first[a], first[b]), r = max(first[a], first[b]);
        int k = __lg(r - l + 1);
        cout << shallower(sp[k][l], sp[k][r - (1 << k) + 1]) << "\n";
    }
}
2
1
2
3

4. The longest calm stretch.

Solution

The same two pointers; keep the maximum of r − l + 1 instead of the count.

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

const int LOG = 19;
int n, K, a[500001], mn[LOG][500001], mx[LOG][500001];

int spread(int l, int r) {
    int k = __lg(r - l + 1), s = r - (1 << k) + 1;
    return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s]);
}

int main() {                                  // the longest calm stretch (max − min ≤ K)
    cin >> n >> K;
    for (int i = 1; i <= n; i++) cin >> a[i], mn[0][i] = mx[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
        }
    int best = 0, l = 1;
    for (int r = 1; r <= n; r++) {
        while (spread(l, r) > K) l++;
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}
3

Quick quiz

Query [3, 12]. Which two entries does lowest read?

len = 10;  k = __lg(10)

A) mn[3][3], mn[3][5] · B) mn[3][3], mn[3][4] · C) mn[4][3], mn[4][12] · D) mn[2][3], mn[2][9]

Answer

A. k = 3 (8 ≤ 10 < 16): [3, 10] and [12 − 8 + 1, 12] = [5, 12].

Interview questions

  1. What is a sparse table? A table of answers for all power-of-two-length ranges, answering idempotent range queries in O(1).
  2. Why does the overlap not matter? Because min (max, gcd…) is idempotent: x ⊕ x = x.
  3. Why can't it do range sums with overlap? Sums count overlapped elements twice; use prefix sums or a disjoint sparse table.
  4. Build and query complexity? O(n log n) time and memory to build, O(1) per query.
  5. Sparse table vs segment tree? Sparse table: faster queries, static data only. Segment tree: O(log n) queries but supports updates and non-idempotent operations.
  6. How do you compute ⌊log₂ len⌋ safely? __lg(len), 31 − __builtin_clz(len), or a precomputed table — not floating-point log2.
  7. Give an application. LCA via Euler tour + RMQ; LCP of suffixes; two pointers with range max − min.

Glossary

Term Meaning Example
Static array An array that never changes after reading the bridges
RMQ Range minimum (or maximum) query lowest bridge
Sparse table mn[j][i] = answer for [i, i + 2^j − 1] the chart
Level j Stretches of length 2^j j = 2: four bridges
__lg(x) ⌊log₂ x⌋, the highest set bit (g++) __lg(6) = 2
Idempotent x ⊕ x = x min, max, gcd
Overlap trick Two overlapping power-of-two stretches cover any range [1,4] and [3,6]
Prefix sums pre[i] = a[1] + … + a[i] tolls
Two pointers Moving a left and a right index forward only calm stretches
Monotone property Still true after shrinking (or growing) a range calm
Euler tour The DFS order with every arrival and return LCA
LCA Lowest common ancestor in a rooted tree homework 3
gcd Greatest common divisor __gcd(12, 18) = 6
xor checksum Folding many answers into one number check ^= …
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Time Limit Exceeded (TLE) Too slow loops
Wrong Answer (WA) A wrong output tolls 16
Sqrt decomposition Splitting an array into √n blocks next episode

Summary

  • mn[j][i] = min of 2^j values from i, built from two halves; O(n log n).
  • Query = min of two overlapping stretches with k = __lg(len): O(1).
  • Only for idempotent operations (min, max, gcd); sums use prefix sums (16 instead of 11 otherwise).
  • Static arrays only; with updates use a segment tree.
  • Monotone window problems = two pointers + O(1) spread checks.

Solutions in C++, Java and Python

Problem L1 · Low Bridges

C++

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

int n, q, h[500001];
ll c[500001];
const int LOG = 19;                            // 2^19 > 5·10^5
int mn[LOG][500001];                           // mn[j][i] = lowest of h[i .. i + 2^j − 1]
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = h[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);   // two halves
}
int lowest(int l, int r) {                     // two overlapping stretches
    int k = __lg(r - l + 1);
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
ll pre[500001];                                // tolls: prefix sums, no overlap
void buildSum() { for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i]; }
ll toll(int l, int r) { return pre[r] - pre[l - 1]; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    build();
    buildSum();
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << lowest(l, r) << " " << toll(l, r) << "\n";
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval; in.nextToken(); int q = (int) in.nval;
        final int LOG = 19;
        int[][] mn = new int[LOG][n + 1];                 // mn[j][i] = lowest of 2^j bridges from i
        long[] pre = new long[n + 1];                     // tolls: prefix sums
        for (int i = 1; i <= n; i++) { in.nextToken(); mn[0][i] = (int) in.nval; }
        for (int i = 1; i <= n; i++) { in.nextToken(); pre[i] = pre[i - 1] + (long) in.nval; }
        for (int j = 1; j < LOG; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                mn[j][i] = Math.min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval;
            int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(len))
            sb.append(Math.min(mn[k][l], mn[k][r - (1 << k) + 1])).append(' ').append(pre[r] - pre[l - 1]).append('\n');
        }
        System.out.print(sb);
    }
}
3 11
4 8
8 2
3 6

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    h = [0] + [int(x) for x in data[2:n + 2]]
    pre = [0] * (n + 1)
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + int(data[n + 1 + i])
    mn = [h]                                    # mn[j][i] = lowest of 2^j bridges from i
    j = 1
    while (1 << j) <= n:
        prev, half = mn[-1], 1 << (j - 1)
        mn.append([0] + [min(prev[i], prev[i + half]) for i in range(1, n - (1 << j) + 2)])
        j += 1
    out, p = [], 2 * n + 2
    for _ in range(q):
        l, r = int(data[p]), int(data[p + 1]); p += 2
        k = (r - l + 1).bit_length() - 1        # floor(log2(len)), exact
        out.append(f"{min(mn[k][l], mn[k][r - (1 << k) + 1])} {pre[r] - pre[l - 1]}")
    print("\n".join(out))

main()
3 11
4 8
8 2
3 6

Problem L2 · Calm Stretches

C++

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

int n, K, a[500001];
const int LOG = 19;
int mn[LOG][500001], mx[LOG][500001];
void build() {
    for (int i = 1; i <= n; i++) mn[0][i] = mx[0][i] = a[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
        }
}
int spread(int l, int r) {                     // max − min of a[l..r] in O(1)
    int k = __lg(r - l + 1), s = r - (1 << k) + 1;
    return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build();
    ll calm = 0;
    int l = 1;
    for (int r = 1; r <= n; r++) {                 // two pointers
        while (spread(l, r) > K) l++;            // too wild: move the start
        calm += r - l + 1;                       // every start l..r works
    }
    cout << calm << "\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval; in.nextToken(); int K = (int) in.nval;
        final int LOG = 19;
        int[][] mn = new int[LOG][n + 1], mx = new int[LOG][n + 1];
        for (int i = 1; i <= n; i++) { in.nextToken(); mn[0][i] = mx[0][i] = (int) in.nval; }
        for (int j = 1; j < LOG; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mn[j][i] = Math.min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
                mx[j][i] = Math.max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
            }
        long calm = 0;
        int l = 1;
        for (int r = 1; r <= n; r++) {
            while (true) {                               // move l while the stretch is too wild
                int k = 31 - Integer.numberOfLeadingZeros(r - l + 1), s = r - (1 << k) + 1;
                if (Math.max(mx[k][l], mx[k][s]) - Math.min(mn[k][l], mn[k][s]) <= K) break;
                l++;
            }
            calm += r - l + 1;
        }
        System.out.println(calm);
    }
}
13

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, K = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:n + 2]]
    mn, mx = [a], [a]
    j = 1
    while (1 << j) <= n:
        half = 1 << (j - 1)
        pm, px = mn[-1], mx[-1]
        top = n - (1 << j) + 2
        mn.append([0] + [min(pm[i], pm[i + half]) for i in range(1, top)])
        mx.append([0] + [max(px[i], px[i + half]) for i in range(1, top)])
        j += 1

    def spread(l, r):
        k = (r - l + 1).bit_length() - 1
        s = r - (1 << k) + 1
        return max(mx[k][l], mx[k][s]) - min(mn[k][l], mn[k][s])

    calm, l = 0, 1
    for r in range(1, n + 1):
        while spread(l, r) > K:
            l += 1
        calm += r - l + 1
    print(calm)

main()
13