cf.completefrontend
ADVANCED DATA STRUCTURES · ADVANCED

Segment tree

A tree over an array where each node stores the sum (or min, or max) of a range, so range questions and single-item updates both take O(log n).

Time O(log n) per query or update, O(n) to buildSpace O(n)3 practice problemsStep-through picture

The idea

Some tasks keep asking two things about an array: "what is the sum of items left to right?" and "item i just changed to v". A plain loop answers a range sum in O(n). A prefix-sum array answers it in O(1), but one change forces you to rebuild it in O(n). A segment tree does both in O(log n).

The tree's root covers the whole array. Each node splits its range in half: the left child covers the first half and the right child the second half, down to leaves that cover one item each. Every node stores the sum of its range, which is just its two children's sums added.

To answer a range question, you use the few nodes whose ranges fit exactly inside the asked range. To update one item, you change its leaf and fix the sums on the path back up to the root. Both touch about log n levels.

An everyday example

Sales reports in a company

Each shop reports its daily sales to its district manager, each district manager reports the district total to a regional manager, and the regions report to the head office. To get the total for a group of neighboring shops, the head office doesn't call every shop: it uses whole district totals where a district is fully inside the group, and only calls single shops at the edges. When one shop corrects its number, only its district, region, and head office totals change.

How the example maps to the code
In the exampleIn the code
A single shop's salesa leaf, this.tree[node] with lo === hi
A manager's totalthis.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1]
A district fully inside the groupleft <= lo && hi <= right
A district with no shop in the groupright < lo || hi < left, which adds 0
A shop correcting its numberupdate(...) fixing totals up the path

From the slow way to segment tree

  1. Start with the two simple tools. A plain array changes an item in one step but needs up to n steps to add up a range. A prefix-sum array adds up any range in one step, but changing one item means fixing up to n prefix sums. With 100,000 items and 100,000 mixed operations, either tool can take about 10 billion steps.
  2. The middle ground is to store sums of some blocks of the array. A range question can then add a few big blocks instead of many items, and an update only has to fix the blocks that contain the changed item. The goal is a set of blocks where every range is made of few blocks and every item sits in few blocks.
  3. Halving gives both. Keep one block for the whole array, one for each half, one for each quarter, and so on, down to single items. That's about log n levels, and each item sits in exactly one block per level, so an update fixes about log n sums. Any range is covered using at most two partly-overlapping blocks per level, so a query also touches about log n levels.
  4. These blocks form a tree. Store it in an array: node 1 covers the whole array, and node k has children 2k and 2k + 1 covering its two halves. A query asks each node one question: is my range outside, inside, or partly overlapping the asked range? An update walks down to one leaf and fixes the sums on the way back up. That structure is a segment tree.

How it works

  1. Store the tree in an array tree of size 4 * n. Node 1 is the root; node k's children are 2k and 2k + 1.
  2. Build: a node covering lo to hi with lo === hi is a leaf holding nums[lo]. Otherwise build both halves around mid and add their sums.
  3. Query left to right at a node covering lo to hi: if the ranges don't overlap, return 0.
  4. If the node's range is fully inside left to right, return its stored sum without going deeper.
  5. Otherwise the ranges partly overlap: return the left child's answer plus the right child's answer.
  6. Update item index: walk down to its leaf, set the new value, and recompute each parent's sum on the way back up.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class SegmentTree {
  2. constructor(nums) {
  3. this.n = nums.length;
  4. this.tree = new Array(4 * this.n).fill(0);
  5. this.build(nums, 1, 0, this.n - 1);
  6. }
  8. build(nums, node, lo, hi) {
  9. if (lo === hi) {
  10. this.tree[node] = nums[lo];
  11. return;
  12. }
  13. const mid = Math.floor((lo + hi) / 2);
  14. this.build(nums, 2 * node, lo, mid);
  15. this.build(nums, 2 * node + 1, mid + 1, hi);
  16. this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  17. }
  19. query(node, lo, hi, left, right) {
  20. if (right < lo || hi < left) return 0;
  21. if (left <= lo && hi <= right) return this.tree[node];
  22. const mid = Math.floor((lo + hi) / 2);
  23. return this.query(2 * node, lo, mid, left, right) + this.query(2 * node + 1, mid + 1, hi, left, right);
  24. }
  26. update(node, lo, hi, index, value) {
  27. if (lo === hi) {
  28. this.tree[node] = value;
  29. return;
  30. }
  31. const mid = Math.floor((lo + hi) / 2);
  32. if (index <= mid) this.update(2 * node, lo, mid, index, value);
  33. else this.update(2 * node + 1, mid + 1, hi, index, value);
  34. this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  35. }
  36. }

How fast it is

TimeO(log n) per query or update, O(n) to build
Extra memoryO(n)

The tree has about log n levels, and a query or update touches only a few nodes per level. Building visits each node once. The array holds at most 4n numbers.

  • Best caseO(1)

    A query for the whole array: the root is fully inside, so the first call returns tree[1].

  • Average caseO(log n)

    A typical query or update touches a few nodes on each of the about log n levels.

  • Worst caseO(log n)

    A range whose two ends cut deep into the tree, such as 1..4 above: 9 calls on 6 items. On 1,000 items, no query makes more than 39 calls.

Common mistakes

  • Sizing the array 2 * n with this recursive layout. For some n the node numbers go past 2n; 4 * n is safe.
  • Returning the wrong "outside" value, such as 0 for a range minimum. Use a value that doesn't change the answer, like Infinity for min.
  • Forgetting to recompute the parent sums after updating a leaf, so queries still see the old value.
  • Using a segment tree when the array never changes. A prefix-sum array (for sums) or a sparse table (for min and max) is simpler and faster then.

When to use it

Look for these clues in a problem:

  • Many range queries (sum, min, max, gcd) are mixed with updates to single items.
  • A prefix-sum array would work if the data never changed, but it does.
  • The input has up to 10^5 items and 10^5 operations, so O(n) per operation is too slow.
  • You need range updates as well, such as "add 5 to items 3 to 9" (a segment tree with lazy updates).

Check yourself

Answer each one in your head first, then open it.

How many calls does the trace's query for 1..4 make?

9. Nodes 1, 2, 3, and 4 are partial, nodes 9, 5, and 6 are inside, and nodes 8 and 7 are outside.

Why isn't an array of 2n slots enough here?

With n = 6, the leaf for index 3 is node 12 and the leaf for index 4 is node 13, which is past slot 2n = 12.

What two changes turn this into a range-minimum tree?

Return Infinity instead of 0 for an outside node, and combine children with Math.min instead of +, in build, query, and update.

After update(1, 0, 5, 3, 9), which stored sums changed?

Four: the leaf, node 12, became 9, node 6 became 14, node 3 became 17, and the root became 29. No other node covers index 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The tree keeps one property: tree[node] is the sum of nums[lo] to nums[hi], the range that node covers. build makes it true: a leaf stores its one item, and every other node stores its two children's sums, whose ranges lo..mid and mid + 1..hi split its own range exactly.

A call query(node, lo, hi, left, right) returns the sum of the items that are in both the node's range and the asked range. If the two don't touch, that's nothing, so 0. If the node's range is fully inside, it's the node's whole sum. Otherwise the two children's ranges split the node's range, so the answer is the sum of their answers. The root call covers the whole array, so it returns exactly the asked range's sum.

update keeps the property. The only sums that include index index belong to the nodes on the path from the root to its leaf. The walk sets the leaf and recomputes each of those nodes from its children on the way back up, so every node is correct again. And a query stays fast because, on each level, only the nodes holding the range's two ends can be partial; every other node is answered or skipped at once.

Going deeper

3 more ideas

Why a query visits only a few nodes

At each level of the tree, at most two nodes partly overlap the asked range: the ones at its left edge and its right edge. Every other node at that level is either fully inside (answered at once) or fully outside (skipped). So a query visits at most about four nodes per level, and there are about log n levels.

Cost

Building visits each of the about 2n nodes once: O(n). A query or an update walks about log n levels with a few nodes per level: O(log n). The array of size 4n is a safe upper bound for any n, so the space is O(n).

Other operations, and range updates

Any operation that combines two halves works: replace + with Math.min, Math.max, or a gcd, and change the "outside" value to one that doesn't affect the answer (Infinity for min, -Infinity for max). To add a value to a whole range quickly, nodes can store a pending "lazy" amount that is pushed down to the children only when a later query or update needs to go below that node.

Work it by hand

Every step in a table, with why

Ask for the sum of indexes 1 to 4 in 6 numbers, then change index 3 from 2 to 9. Each row is one call of query or update.

nums = [4, 1, 7, 2, 5, 3], then query(1, 0, 5, 1, 4), then update(1, 0, 5, 3, 9)

StepCallnodelo..hiOverlap with the rangeReturns or storesWhy
1query10..5partialasks both childrenThe root holds 22, the sum of everything, but the range 1..4 covers only part of it, so it splits at mid = 2.
2query20..2partialasks both childrenNode 2 covers 0..2, and index 0 is outside the range, so go deeper.
3query40..1partialasks both childrenIndex 0 is out and index 1 is in, so split again.
4query80..0outside0hi = 0 < left = 1, so this leaf adds nothing.
5query91..1inside1Fully inside: return the stored value. Node 4 now returns 0 + 1 = 1.
6query52..2inside7Fully inside. Node 2 returns 1 + 7 = 8.
7query33..5partialasks both childrenNode 3 covers 3..5, but index 5 is past right = 4.
8query63..4inside7Fully inside: its stored sum 2 + 5 = 7 is used without visiting its two leaves.
9query75..5outside0right = 4 < lo = 5. Node 3 returns 7, and the root returns 8 + 7 = 15.
10update10..5index 3 > mid 2go rightNow change index 3. It is past the root's mid, so walk into the right child.
11update33..5index 3 <= mid 4go leftIndex 3 is in the left half of 3..5.
12update63..4index 3 <= mid 3go leftIndex 3 is in the left half of 3..4.
13update123..3leaf2 becomes 9The leaf stores the new value. On the way back up, node 6 becomes 9 + 5 = 14, node 3 becomes 14 + 3 = 17, and the root becomes 12 + 17 = 29.

The query returns 15, which matches 1 + 7 + 2 + 5, after 9 calls. The update changes 4 stored sums, one per level. Asking for 1..4 again now returns 22, which matches 1 + 7 + 9 + 5.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Segment treeO(log n)O(n)Per query or update, after an O(n) build. Pick it for range sums, mins, or maxes mixed with updates, or when you need lazy range updates.
Fenwick treeO(log n)O(n)Sums (or anything that can be subtracted) with single-item updates. Shorter code and only n + 1 numbers.
Prefix-sum arrayO(n)O(n)That O(n) is the cost of an update; a query is O(1). Pick it when the array rarely or never changes.
Loop over the rangeO(n)O(1)That O(n) is the cost of a query; an update is O(1). Fine for a few hundred items or a handful of queries.

Extra memory: O(n): the array has 4n slots. For n = 6 the highest node used is 13, more than 2n = 12, which is why 4n is used. Recursion adds O(log n) for the call chain.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Segment tree and the other approaches, on a scale where each line up is 10 times more steps.
  • Segment tree, Fenwick tree O(log n)
  • Prefix-sum array, Loop over the range O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Segment tree31020
Fenwick tree31020
Prefix-sum array101,0001 million
Loop over the range101,0001 million

Inputs that need care

5 tricky inputs
An empty array: nums = []
build is called with lo = 0 and hi = -1. mid is -1, the same range is built again, and the recursion never ends until a RangeError. Check for an empty array before building.
A length that isn't a power of two, such as 6
The halves have uneven sizes, so node numbers can jump past 2n: here up to 13. The 4 * n array is always big enough.
left > right, such as query(1, 0, 5, 3, 1)
Every node ends up outside, and it returns 0 after 3 calls. Decide whether that means an empty range or a caller bug, and swap or reject the bounds if needed.
One item: nums = [42]
The root is a leaf. query and update both stop at the first call.
Adding to an item instead of setting it
update sets the leaf to value. To add delta, keep a copy of nums and call update with nums[index] + delta, or change the leaf line to +=.

Variations and follow-ups

Twists interviewers add

Min, max, and other combines

Replace + with Math.min, Math.max, or a gcd, and return a neutral value for "outside": Infinity for min, -Infinity for max, 0 for gcd. The structure and the O(log n) bound stay the same.

Lazy range updates

To add v to every item in a range, stop at nodes fully inside the range, add v times their length to their sum, and write v into a lazy array for that node. Push the lazy value down to the children only when a later call needs to go below that node. Range updates then cost O(log n) too.

Bottom-up without recursion

Put the leaves at tree[n] to tree[2n - 1] and fill each parent i from tree[2i] and tree[2i + 1]. Queries walk two indexes up from both ends of the range. It uses 2n slots and no recursion.

Several values per node

A node can store a small record instead of one number. For the largest run sum in a range, store the total, best prefix, best suffix, and best run, and combine two children with a few Math.max calls.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "sum, min, or max of a range" mixed with "update an item", plus limits like 10^5 items and 10^5 operations, where O(n) per operation is too slow.
  • Explain the three cases of query (outside, inside, partial) and why only two nodes per level can be partial: the ones holding the range's two ends.
  • Test a query for the whole array, a one-item range, and an update followed by a query that covers the changed item. Also try a length like 6 that isn't a power of two.
  • The usual follow-up is "what if you add to a whole range?". Answer with lazy updates: store pending additions on fully-covered nodes and push them down only when needed.
  • Another follow-up is "why 4n?". The tree's height is ceil(log₂ n), so the last level can need up to about 2 × 2^ceil(log₂ n) slots, which is less than 4n.

Where frontend code uses it

The same idea in real UI code
  • Charts and timelines that let you edit data points while showing totals or extremes over the visible range can keep a segment tree so each edit and each zoom query stays fast on large datasets.
  • Virtualized lists with rows of different, changing heights need "total height of rows 0 to k" after each row resizes; a segment tree (or a Fenwick tree) answers that in O(log n).
  • Collaborative editors and code editors use balanced trees over text chunks that store per-node totals (characters, line counts) for the same reason: fast "what is at offset x" queries while the text keeps changing.

Related algorithms