rangeupdates

Range updates are operations that modify every element within a contiguous index interval of an array or sequence. The most common form is a range addition, where a fixed value is added to each element in the range [l, r]. Range updates are fundamental in many algorithms because they enable bulk modifications without touching each element individually, which would be inefficient for large data sets.

Supporting fast range updates and fast range queries requires specialized data structures. The segment tree with lazy propagation is a standard solution, performing updates and queries in O(log n) time by postponing work until needed. Fenwick trees (binary indexed trees) can also support range updates and range queries through combinations of trees or difference-based methods, often with O(log n) per operation.

Common variants include range addition with sum queries, where one updates a range by adding a value and later asks for the sum over a range. Range assignment, where all elements in a range are set to a given value, is more complex and typically implemented with lazy tags indicating both addition and assignment. Other aggregates such as minimum or maximum can also be maintained with appropriate structures.

In practice, range updates are used in simulations, databases, and computational geometry to apply bulk changes efficiently and then retrieve aggregated results without recalculating from scratch.