Range queries

Prefix sums are perfect when values don't change, but one update changes every later prefix sum. A Fenwick tree stores overlapping blocks of sums, so both a single update and a prefix sum query take O(log n). It uses indexes starting at 1, so the lowest 1 bit of an index gives the size of its block.

To get a prefix sum, add the block ending at the current index, then clear the index's lowest 1 bit, and repeat. Those blocks exactly cover the prefix. To add to one position, walk up through the blocks that contain it. Index 0 needs special care: an update loop that starts at 0 and adds the lowest 1 bit never moves.

A segment tree splits the index range in half again and again. Each node stores a summary of its range, and a query combines the summaries of a few non-overlapping ranges. The combining operation must give the same result however you group it, and you need a neutral value for empty parts. Sum uses 0, minimum uses infinity, and maximum uses negative infinity.

A standard segment tree handles single updates and range queries in O(log n) time, using O(n) space. Lazy propagation adds range updates by recording updates to apply later. You also need correct rules for combining pending updates and applying them to a summary. "Store a lazy value" isn't a complete design.

Coordinate compression replaces values with their rank when only their order matters. It keeps comparisons, not distances. If your algorithm uses the actual gaps between values, keep those separately.

Before reaching for an advanced structure, check whether you know all queries in advance, whether the data ever changes, or whether you only need a few operations. Sorting the queries, prefix sums, or a monotonic deque may solve a simpler version with much less code.

Practice: LC 307 Range Sum Query Mutable, LC 315 Count of Smaller Numbers After Self, LC 327 Count of Range Sum, LC 218 The Skyline Problem. The last three can be solved several ways; compare what each way keeps track of.

Check your understanding: What does one node store? Why can the pieces of a query be combined in that order? Does an update set a value or add to it? Does compression keep what your operation needs?