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); answermin(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
- What is a sparse table? A table of answers for all power-of-two-length ranges, answering idempotent range queries in O(1).
- Why does the overlap not matter? Because min (max, gcd…) is idempotent: x ⊕ x = x.
- Why can't it do range sums with overlap? Sums count overlapped elements twice; use prefix sums or a disjoint sparse table.
- Build and query complexity? O(n log n) time and memory to build, O(1) per query.
- 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.
- How do you compute ⌊log₂ len⌋ safely?
__lg(len),31 − __builtin_clz(len), or a precomputed table — not floating-point log2. - 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 (
16instead of11otherwise). - 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