Skip to content
Back to Data StructuresAll lessons

Data Structures

Segment Tree

build: O(n) once · update: O(log n) · range query: O(log n) — both far faster than recomputing a range from scratch (O(n)) after every change.

The idea, in plain English

A segment tree is like a company's reporting chain, built to answer 'what's our total?' instantly. Every employee, called a leaf, reports one number. Each manager's number is just their two direct reports added together. This keeps going up, level by level, until the person at the top holds the grand total of everyone below. If you change one employee's number, only the managers directly above them need to redo their math, not the whole company.

How it works

  1. 1Build a tree where each leaf holds one array value, and each parent holds the combined result (here, the sum) of its two children.
  2. 2The node at the top ends up holding the combined result for the whole array — for a sum tree, the grand total.
  3. 3update(i, value): change one leaf's value, then walk back up to the top, recomputing each ancestor along the way.
  4. 4query(l, r): combine only the handful of nodes that exactly cover the range [l, r), skipping everything outside it.

When you'd use it

Use a segment tree for frequent range queries, like sum, min, or max over a range, mixed with frequent updates to individual elements. For example, a leaderboard that must answer 'what's the total score between rank 10 and 50?' right after every new score comes in.

Common beginner mistakes

  • Don't reach for a segment tree when the array never changes. A precomputed prefix-sum array answers range-sum queries just as fast, with much simpler code.
  • Remember that after update(i, value), every ancestor of that leaf must be recomputed on the way back up. If you skip this, the tree quietly keeps stale totals.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Total sum: 36
Sum of indices 1..3: 15
After update, total: 131
After update, indices 1..3: 110

See it in motion

Watch it total upSegment treesum [1,4)build: O(n) once · update: O(log n) · range query: O(log n) — both far faster than recomputing a range from scratch (O(n)) after every change.
Array (query range shaded)
10
31
52
73
94
115

Build bottom-up: each parent = sum of its two children.

[1,4)
Range
0
Running sum
1/22
Step
0.0s
Time
Building sumExaminingCovers rangeSkipped

Not sure this is the right topic? See the learning paths → or where this leads →