~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Sparse table (static RMQ)
O(n log n) build, O(1) idempotent range queries (min/max/gcd).
Notes
Recognise it when: you have a static array and many range-min, range-max or range-gcd queries.
st[k][i] = the answer on [i, i + 2^k). Build it in O(n log n). To query [l, r), let k = (r - l).bit_length() - 1 and take op(st[k][l], st[k][r - 2^k]), which is O(1) for idempotent operations.
Gotchas: it doesn't support updates. For sums, use prefix sums instead.
2 problems
Advanced & competitive
Range queries Fenwick trees, segment trees, sparse tables.
Sparse table (static RMQ)
- Basics: build a sparse table basics py · c++ · java easy
- Tide gauge: rise and fall between two hours py · c++ · java easy