Segment Tree

Hierarchical aggregates for dynamic range queries

Store an answer for every power-of-two segment

Each leaf represents one array element, and every internal node combines the answers of its two children. A query interval is decomposed into a small set of disjoint nodes whose segments fit completely inside it.

Try it

Choose a range and sum a few precomputed segments instead of scanning every value.

A point update changes one leaf and recomputes ancestors to the root. Both range query and point update touch O(log n) tree levels; the complete structure uses O(n) memory.

General form: replace sum with any associative combine operation, such as minimum, maximum, greatest common divisor, or a custom record. Lazy propagation extends the structure to range updates.

For prefix sums with smaller constants, compare the Fenwick Tree.