Skip to content

level 6 · Trees

Segment Tree

Every node stores the answer for a whole range — so a range query stops early.

13 min 110 XP

what is it

Start here

The question: what's the sum of a[2..5]? Easy — add them up. O(n). Now answer it a million times, on an array that keeps changing. Suddenly O(n) per question is a disaster.

You might reach for a prefix-sum array: precompute running totals and every range sum becomes one subtraction, O(1). Beautiful — until someone changes a single value, and you have to rebuild the entire prefix array. O(n) per update. You've just moved the pain.

A segment tree gives you both. Every node stores the answer for a **range**: the leaves are single values, and each parent holds the sum of its two children. The root holds the sum of everything.

Now watch the query. It walks down, and the moment a node's range sits **entirely inside** the question, it grabs that one pre-computed number and stops. It doesn't descend to the leaves. Those green nodes in the visualization each hand back an entire range at once — that early stop is exactly where the log n comes from.

And because each value only affects the log n nodes above it, changing one number is O(log n) too. Both operations logarithmic — that's the deal a prefix-sum array can't offer.

real-life analogy

Picture it

A company that already knows its own subtotals

Ask a big company for the total salary of three departments. Nobody adds up every employee — each department already knows its own subtotal, and each division knows the sum of its departments. You collect three numbers, not three thousand. And when one person gets a raise, only their department, division and the company total need updating — not everybody else.

interactive visualization

Watch it run

Built first, then queried for the sum of a[2..5]. Watch how few nodes it touches.

Array: 5, 3, 8, 2, 7, 1, 6, 4. Question: what's the sum of a range, like a[2..5]? Adding them up each time costs O(n). A segment tree answers it in O(log n) — and unlike a prefix-sum array, it still works when values change.

step 01/11

  • comparing
  • in the output
  • target · placed
  • on the path
  • ruled out
1// Every node stores the SUM of a range of the array.
2function build(a, lo, hi) {
3 if (lo === hi) return new Node(a[lo], lo, hi); // a leaf
4
5 const mid = (lo + hi) >> 1;
6 const node = new Node(0, lo, hi);
7 node.left = build(a, lo, mid);
8 node.right = build(a, mid + 1, hi);
9 node.sum = node.left.sum + node.right.sum;
10 return node;
11}
12
13// Sum of a[l..r] — without touching most of the array.
14function query(node, l, r) {
15 if (r < node.lo || node.hi < l) return 0; // no overlap
16 if (l <= node.lo && node.hi <= r) return node.sum; // fully inside
17
18 return query(node.left, l, r) + query(node.right, l, r);
19}

variables right now

array
5 3 8 2 7 1 6 4
n
8
comparisons 0moves 0

the dry run · every step, in words

11 steps

complexity

What it costs

best case
O(log n) query
average
O(log n) update
worst case
O(n) to build
extra memory
O(n)

Build once in O(n). Then every range query and every single-value update is O(log n). A prefix-sum array gives O(1) queries but O(n) updates; a plain array gives O(1) updates but O(n) queries. The segment tree is the one that's fast at both.

  • O(1)
  • O(log n) · this one
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Descending all the way to the leaves on every query.

    Then it's just an O(n) scan with extra steps. The whole speed comes from *stopping* the moment a node's range is fully inside the query and taking its stored answer.

  • Getting the three overlap cases wrong.

    No overlap → return 0 and abandon the branch. Fully inside → return the stored sum, stop. Partial → split and ask both children. Muddle these and you'll double-count or miss ranges.

  • Using a prefix-sum array when the data changes.

    Prefix sums are perfect for a static array and terrible for a changing one — every update rebuilds it. If values change, that's exactly what a segment tree is for.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+110 XP

01What does each node of a segment tree store?

02Why is a range query O(log n) rather than O(n)?

03What can a segment tree do that a prefix-sum array can't?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.