Segment Tree: Range Sum
Hard+110 XPStore the sum of every range in a tree so a range-sum query reads a few nodes (O(log n)) instead of adding every element.
No visualization loaded.
Watch
—
Press Run to begin.
Suppose you have a row of numbers and people keep asking 'what's the sum from position 1 to position 5?' Adding those up one by one every time is slow if the row is long and the questions never stop. A segment tree pre-organizes the row into a tree where EVERY node stands for a range of the row and already knows the sum of that range. The root knows the sum of the whole row. Its two children split the row in half and each knows its half's sum. That keeps splitting until the leaves, which are the single numbers. To answer 'sum from l to r,' you walk down from the root and grab a small handful of nodes whose ranges exactly tile the part you asked about — so instead of adding maybe a thousand numbers, you add just a few stored sums.
▸Why store sums of ranges at all?
Because then a range question becomes 'read a few boxes' instead of 'add up everything.' If a node already says '[2..5] sums to 14,' and that whole range is inside what you asked for, you just take 14 — you skip looking at the four numbers individually. Pre-computing these range sums once lets every later query reuse them, so you do far less adding per question.
▸How is a query for [l..r] actually answered?
You start at the root and check each node's range against [l..r]. Three cases: if the node's range is completely OUTSIDE [l..r], ignore it and its whole subtree. If it's completely INSIDE [l..r], take its stored sum and stop — no need to go deeper. If it only PARTLY overlaps, go into both children and repeat. The handful of 'completely inside' nodes you collect tile exactly the range you wanted, and you add up just their sums.
▸Why is a query O(log n) and not O(n)?
The tree is only about log n levels deep (each level splits the range in half). At each level the query touches at most a couple of nodes — the rest of each level is either fully inside (taken whole, no recursion) or fully outside (pruned). So the number of nodes you visit grows with the DEPTH (log n), not with how many elements are in the range. Even a range covering thousands of elements is answered by a few node reads.
▸How does it beat a plain prefix-sum array when the data CHANGES?
A prefix-sum array answers range sums in O(1), which sounds better — but if you change a single number, you have to rebuild all the prefix sums after it, which is O(n) per update. A segment tree updates in O(log n): changing one number only fixes the sums along the single path from that leaf up to the root. So when the data keeps changing (point updates mixed with queries), the segment tree's O(log n) update wins big over the prefix array's O(n).
How the work grows
O(log n) per query (O(n) to build) is excellent — barely grows. The tree has about log n levels, and a range query visits only a constant number of nodes per level (the rest are taken whole or pruned), so a query is O(log n). A point update fixes just the path from a leaf to the root — also O(log n). Building the tree once is O(n), and storing roughly 2n nodes is O(n) memory. This beats re-adding every element (O(n) per query) and beats a prefix-sum array's O(n) rebuild whenever a value changes.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.