Skip to content
AITroveRead. Build. Understand.
Reading list

Range Queries

Point updates and repeated interval queries.

Point updates and repeated interval queries. Work through the operation contract, runnable case, and cost before selecting the structure for a real workload.

Lessons

Practice and next steps

Sparse tables: precompute immutable range minima

Persistent segment trees: retain old range-sum versions

Sparse coordinate segment tree: allocate only visited paths

Lazy segment tree: add to a range and query its minimum

Two-dimensional Fenwick tree: update cells and sum rectangles

Two Fenwick trees: add across ranges and query sums

Square-root blocks: update one capacity and sum a range

Merge-sort trees: count readings below a threshold in one interval

Disjoint sparse tables: immutable sums with constant-time queries

Li Chao trees: minimum linear tariff at a chosen quantity

Coordinate compression: preserve order with dense integer ranks

Fenwick frequency index: select the kth stored key

Mo ordering: count distinct scan codes across an offline query batch

Two-dimensional prefixes: constant-time static rectangle sums

Segment tree beats: cap a range while retaining its sum

Wavelet matrices: count frequencies and find subarray quantiles

Compressed 2D Fenwick trees: toggle known points and count rectangles

Segment-tree stabbing indexes: list intervals active at one point

Two-dimensional segment trees: correct sensors and sum rectangles

Range-majority indexes: verify a candidate before returning it

Range-mode indexes: combine complete-block modes with fringe candidates

Persistent range MEX: search last occurrences in prefix versions

Range XOR bases: merge linear spans in a segment tree

Affine lazy segment trees: compose range calibration before summing

Persistent subarray ranks: subtract prefix frequency trees

Maximum-subarray segment trees: preserve the crossing burst

Li Chao interval offers: limit each line to its valid minutes

Persistent range-distinct counts: keep only the latest position active

Editable substring fingerprints: join hashes in a segment tree

Curriculum

Point updates and repeated interval queries.

  1. 1Fenwick trees: update points and query prefix totals
  2. 2Segment trees: combine child ranges after updates
  3. 3Sparse tables: precompute immutable range minima
  4. 4Persistent segment trees: retain old range-sum versions
  5. 5Sparse coordinate segment tree: allocate only visited paths
  6. 6Lazy segment tree: add to a range and query its minimum
  7. 7Two-dimensional Fenwick tree: update cells and sum rectangles
  8. 8Two Fenwick trees: add across ranges and query sums
  9. 9Square-root blocks: update one capacity and sum a range
  10. 10Merge-sort trees: count readings below a threshold in one interval
  11. 11Disjoint sparse tables: immutable sums with constant-time queries
  12. 12Li Chao trees: minimum linear tariff at a chosen quantity
  13. 13Coordinate compression: preserve order with dense integer ranks
  14. 14Fenwick frequency index: select the kth stored key
  15. 15Mo ordering: count distinct scan codes across an offline query batch
  16. 16Two-dimensional prefixes: constant-time static rectangle sums
  17. 17Segment tree beats: cap a range while retaining its sum
  18. 18Wavelet matrices: count frequencies and find subarray quantiles
  19. 19Compressed 2D Fenwick trees: toggle known points and count rectangles
  20. 20Segment-tree stabbing indexes: list intervals active at one point
  21. 21Two-dimensional segment trees: correct sensors and sum rectangles
  22. 22Range-majority indexes: verify a candidate before returning it
  23. 23Range-mode indexes: combine complete-block modes with fringe candidates
  24. 24Persistent range MEX: search last occurrences in prefix versions
  25. 25Range XOR bases: merge linear spans in a segment tree
  26. 26Affine lazy segment trees: compose range calibration before summing
  27. 27Persistent subarray ranks: subtract prefix frequency trees
  28. 28Maximum-subarray segment trees: preserve the crossing burst
  29. 29Li Chao interval offers: limit each line to its valid minutes
  30. 30Persistent range-distinct counts: keep only the latest position active
  31. 31Editable substring fingerprints: join hashes in a segment tree
Storage details