Segment Trees: Dynamic Interval Queries at O(log n)

Concepts: pySegmentTree, pyRangeCoverageQuery, pyLazyPropagation

Prefix sums and sorted-list scans handle static and append-only workloads. But when you need O(log n) range updates AND O(log n) range queries on a dataset where both insertions and deletions happen continuously, you need a segment tree. The segment tree partitions the value space (not the data) into a binary tree of ranges, allowing you to update a range and query a range in O(log n) each. This is the data structure behind range max, range sum, and coverage queries in dynamic systems. Segment Tree for Interval Coverage The critical feature of this segment tree is that it supports removals (decrements), not just additions. This is what sorted-list approaches cannot do efficiently for coverage queries. The lazy propagation ensures that O(log n) updates do not cascade into O(n) child updates