A segment tree answers range questions — sum, min, max, gcd, xor — on any interval [l, r] of an array in O(log n) time and re-updates any single element in O(log n). Enter an array, pick an aggregate, then run a range query or point update and watch which internal nodes contribute or get rewritten.
contributed to query partial (walked into) rewritten on update
A prefix-sum array answers sum(l, r) in O(1), but any point update forces O(n) work to rebuild the suffix. A Fenwick tree fixes updates but only handles group operations. A segment tree is the general answer: any operation whose combine step is associative — sum, min, max, gcd, xor, matrix product, string-hash merge — plugs in with the same skeleton. The tree caches an aggregate on every internal node covering a contiguous range; queries walk from the root, take the whole aggregate at any node fully inside [l, r], and recurse into children only where the range straddles the split point. That guarantees O(log n) touched nodes per operation.
The contributing nodes light up green — count them and you'll see it never exceeds 2 · ⌈log₂ n⌉. On a point update, the yellow chain from leaf back to root is exactly the ⌈log₂ n⌉ + 1 nodes whose stored aggregate changed. Add lazy propagation on top and the same tree handles range updates too — but the point-update / range-query pair below already covers the majority of contest problems.