Segment Tree

Answers range-sum queries in logarithmic time and stays correct under updates. Each node stores the sum of one interval; a query decomposes into a handful of covering nodes, and an update walks a single root-to-leaf path. Prefix sums are faster for static data, and useless the moment an element changes.

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(n)