Segment trees

Store an aggregate for every interval\n\nA segment tree is appropriate when an array receives updates and must answer associative range queries such as sum, minimum, maximum, or gcd. Each node represents an interval and stores that interval's aggregate; its children represent the two halves. Build recursively or iteratively from leaves. For a query, return the node value on total overlap, the operation identity on no overlap, and combine child answers on partial overlap. For a point update, change one leaf and recompute aggregates along its path to the root. The invariant is that every node always equals the aggregate of exactly its covered interval. Build costs O(n), each point update and range query costs O(log n), and storage is O(n) (often allocated as about 4n recursively). For immutable range sums, prefix sums give O(1) queries and are simpler; choose the tree only when updates or another aggregate justify it. Test single elements, full ranges, empty overlap identity, repeated updates, and non-commutative operations if order matters.