Segment trees

Range query AND point update, both O(log n). Refuse the array's "fast query OR fast update" choice.

A tree of range aggregates

• Root = whole array's sum; children = halves; leaves = elements
• Query [i,j]: node fully inside → take its sum; partial → split; outside → skip
• Any range = O(log n) canonical segments
• Update: fix the O(log n) ancestors on one path

Watch a query decompose

Sum of [2:6] = 3 canonical segments (green), not 5 element reads.

Wins on mixed workloads

50/50 query/update: segment tree 6× faster than raw array, 100× faster than prefix sums.

When (and when not)

• Yes: mutable data + range queries (sum/min/max/gcd), lazy propagation for range updates
• No, static data: prefix sums (O(1) query)
• No, only prefix sums: Fenwick tree (next — leaner)

Takeaway

Wins by having no slow operation. Benchmark the workload, not one op. Next: the Fenwick tree — the lean sum specialist.