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.