Segment Tree

Prefix sums answer range sums in O(1), until the array changes and you must rebuild them in O(n). A segment tree handles both range queries and updates in O(log n), which is why it shows up in leaderboards, monitoring dashboards and half of all contest problems.

advanced⏱ 15 min read

←Builds on

5Fenwick Tree (Binary Indexed Tree)A Fenwick tree answers prefix sums; a segment tree also answers min or max on any range [L, R], which Fenwick cannot.5Trees: Concepts, Properties, TraversalsA segment tree is a binary tree in which every node covers a range.

Leads to→

This is where the roadmap ends. Look back at how far you came.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01A tree of range sums

Put the array in the leaves of a complete binary tree. Every internal node stores the sum of its two children, so each node is responsible for one contiguous range: the root covers everything, its children cover the halves, and so on.

To answer sum(l..r), combine the few nodes whose ranges lie fully inside [l, r] and together tile it exactly. There are at most two such nodes per level, so a query touches O(log n) nodes.

In the figure, sum(2..6) uses the nodes [2–3], [4–5] and [6]: three nodes instead of five numbers. On a million elements it is about 40 nodes instead of a million.

Store the tree in an array of size 4n: node v has children 2v and 2v+1, just like a binary heap. (Exactly 2n is enough only when n is a power of two, or with the iterative bottom-up layout.)

Each node shows its sum and, below it, the range it covers.

02Point updates and other operations

To change a[i], update its leaf and then walk up to the root, recomputing each ancestor as the sum of its two children. Only the log n + 1 nodes on that path change.

Nothing here depends on the operation being +. Any associative operation works: minimum, maximum, gcd, xor, even "maximum subarray sum" if each node stores a few extra numbers. Swap the combine function and keep the rest.

With lazy propagation, a node can also remember a pending update for its whole range ("add 5 to all of [l, r]") and pass it down only when needed. That gives range updates in O(log n) as well. Learn the basic version first.

03Writing it: the recursive version

The usual contest implementation is recursive. build(v, l, r): if l == r, store a[l]; otherwise build both halves at m = (l + r) / 2 and set t[v] = t[2v] + t[2v+1].

query(v, l, r, ql, qr) has three cases:

[l, r] lies outside [ql, qr]: return 0;
[l, r] lies fully inside [ql, qr]: return t[v] at once;
otherwise: return the sum of both children.

update(v, l, r, i, x) goes down to the leaf of i and recomputes t[v] on the way back up. Every call costs O(log n).

If you only need sums with point updates, the shorter Fenwick tree from its own lesson in the Trees stage is enough; the segment tree is the tool when you need min, max or anything else that cannot be "subtracted".

Cost at a glance

BuildO(n)

Range queryO(log n)

Point updateO(log n)

MemoryO(n)

Remember

Each segment tree node stores the aggregate of one contiguous range, and any range splits into O(log n) such nodes.
A point update changes one leaf and its ancestors only, so it also costs O(log n).
Any associative operation works (sum, min, max, gcd): change the combine function and keep the rest.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: During the query, count the highlighted nodes: far fewer than the numbers in the range. During the update, only one path from root to leaf lights up.

Interactive visualizerfocus here, then space ← →

Segment tree (sum)

Array

52713648

A segment tree answers range-sum queries and point updates in O(log n). Each node stores the sum of a contiguous range.

Pseudocode

 1 leaves hold the array; each internal node = sum of its two children 2 build: fill leaves, then t[v] = t[2v] + t[2v+1] bottom-up 3 query(l,r): combine O(log n) canonical nodes that tile the range 4   take a node fully inside the range; recurse otherwise 5 update(i): change the leaf, then refresh its ancestors

1 / 1

Check

Three questions. Pick an answer to see why.

You need range minimum queries on an array that also receives point updates. What fits best?

In a segment tree over 16 elements, how many nodes change when you update one element?

In the recursive query, the current node covers [l, r] and lies fully inside [ql, qr]. What does it do?

Practice

Real problems to lock it in, easiest first.

CSESStatic Range Sum Queries beginner↗LeetCodeRange Sum Query - Mutable intermediate↗CSESDynamic Range Sum Queries intermediate↗CSESDynamic Range Minimum Queries intermediate↗CSESHotel Queries advanced↗