Segment tree

A binary tree organizing a fixed sequence into recursively subdivided contiguous intervals. Each node stores an aggregate for its interval. Range queries and point updates visit logarithmically many nodes; range-update variants store additional information such as a coverage count to maintain the length of a union of active intervals.

A lazy segment tree augments a segment tree with lazy propagation, allowing compatible interval updates and interval aggregate queries in logarithmic time.

Lazy propagation postpones an interval update at an internal node until its descendants are needed. Each node retains both its current aggregate and a pending update tag, which is composed with later tags.