Module 36
Advanced Data Structures
Range queries on changing data: Fenwick trees, segment trees, lazy propagation, sparse tables, ordered maps and coordinate compression.
Prefix sums answer range sums in O(1), but a single update forces an O(n) rebuild. When queries and updates are interleaved, you need a structure that keeps partial answers for blocks of the array, so both operations touch only O(log n) blocks.
This module builds the Fenwick (binary indexed) tree for sums and counts, the segment tree for any associative operation (min, max, sum, gcd), explains lazy propagation for range updates and sparse tables for static minimums, and shows how ordered maps and coordinate compression handle large or sparse values. The problems use them for counting inversions, smaller elements, range sums and constrained subsequences.
Best after: Prefix Sum, Binary Trees
Where this shows up in real systems
- System Design · System 12.36 — Real-Time Leaderboard — A Fenwick or segment tree over score ranges answers "what is my rank?" in O(log n).
- System Design · System 12.38 — Hotel Reservation System — Checking a new booking against existing ones with a sorted map.
Part 1
Learn the ideas
- 36.1Fenwick Trees (Binary Indexed Trees)bit[i] stores the sum of a block ending at i whose length is the lowest set bit of i. A prefix sum adds O(log n) blocks; an update fixes O(log n) blocks.16 min
- 36.2Segment TreesA binary tree over the array where each node stores the answer for a segment. Queries combine O(log n) nodes; updates change one leaf and its ancestors.16 min
- 36.3Ordered Maps and Coordinate CompressionTreeMap gives sorted keys with floor/ceiling in O(log n). Coordinate compression maps large or negative values to 0..k − 1 so they can index a Fenwick or segment tree.10 min
Part 2
Solve the problems
Work through them in order. Each one shows the pattern it teaches.
A Fenwick tree behind a class: point updates and range sums in O(log n).
Scan from the right, counting with a Fenwick tree over (compressed) values.
Merge sort counting with a different comparison (nums[i] > 2 × nums[j]) before merging.
Prefix sums turn "subarray sum in [lower, upper]" into counting pairs of prefixes, done with merge sort.
An ordered map answers "does this overlap the nearest bookings?" in O(log n).
A segment tree over values answers "best LIS ending at a value in [v − k, v − 1]" in O(log V).