Algorithms · 12 min

Segment tree

Build a tree of totals over a ramen shop’s daily sales, then answer any “days l to r” question and absorb any change in about 20 steps for a million days.

A ramen shop in Osaka logs how many bowls it sells each day. Its dashboard has one box: pick two days, see how many bowls were sold from the first to the last. And the numbers keep changing: today’s count goes up with every bowl, and yesterday’s gets corrected when someone finds a missing receipt.

With 8 days, a loop over the range is fine. Now imagine logging every minute instead of every day. Two years of minutes is about a million numbers, and a loop reads up to a million of them per question.

In this article you build, by hand, a structure that answers questions like this by reading a few dozen stored numbers instead of a million, and absorbs a change by fixing about 20. You will see exactly where those numbers come from. You only need 8 days and some addition.

Eight days on the page

Here are the shop’s 8 days. They are numbered from 0, the same way the demo numbers them.

Step 1: pair up neighbours and write down each pair’s total. Days 0–1: 12 + 7 = 19. Days 2–3: 20 + 5 = 25. Days 4–5: 9 + 14 = 23. Days 6–7: 3 + 18 = 21.

Step 2: pair up the pairs. Days 0–3: 19 + 25 = 44. Days 4–7: 23 + 21 = 44.

Step 3: pair those. Days 0–7: 44 + 44 = 88. That is all 8 days, and you can check it by adding the row of bowls above.

level 0                 days 0–7: 88
level 1       days 0–3: 44                days 4–7: 44
level 2  0–1: 19       2–3: 25        4–5: 23       6–7: 21
level 3 12     7      20     5        9     14      3     18
       day 0  day 1  day 2  day 3   day 4  day 5  day 6  day 7

You did 7 additions and now hold 15 numbers: the 8 days plus 7 totals. For any number of days n, the tree has 2n − 1 boxes. A million days costs about two million numbers, which is fine.

If n is not a power of 2, say 7 days, the halves are just uneven: days 0–3 and 4–6, then 4–5 and day 6 on its own. Day 6 becomes a leaf one level higher than the others. Still 2 × 7 − 1 = 13 boxes.

Asking for days 1 to 6

The question: how many bowls were sold from day 1 to day 6, both included? A loop adds 6 numbers. The tree lets you grab whole boxes instead of single days.

To find those boxes without staring at a picture, start at the root and ask one question of each box you meet:

• All its days inside the range? Use its stored total and don’t look below it.
• All its days outside? Skip it and everything below it.
• Partly inside? Split it: ask the same questions of its two children.

For days 1–6, the root splits, then both 0–3 and 4–7 split. Below them, 2–3 and 4–5 are fully inside and get used whole. Only the two edges, 0–1 and 6–7, split again: they give day 1 and day 6, and skip day 0 and day 7.

That walk looked at 11 boxes to add 4 numbers. On 8 days that is no better than a loop. The win comes when boxes are big: one fully-inside box can stand in for thousands of days in a single read.

A tour group on day 3

Day 3 was a quiet 5 bowls when you built the tree. Then someone finds the receipt for a tour group, and day 3 becomes 15. Some stored totals are now wrong.

Fix them from the bottom up, each by adding its two children again. Day 3 becomes 15. Days 2–3 becomes 20 + 15 = 35. Days 0–3 becomes 19 + 35 = 54. The root becomes 54 + 44 = 98, which is the old 88 plus the extra 10 bowls.

Four fixes for 8 days. The number of fixes is the number of levels, not the number of days. So the only question left is: how many levels does a big tree have?

Why a million days is only 21 levels

Going up one level, boxes get twice as wide, so there are half as many. Count how many times you halve 8 to reach 1: 8 → 4 → 2 → 1 is 3 halvings, and the tree has 4 levels, one more than the halvings.

For a million, halving 20 times gets you to 1, because 2²⁰ is 1,048,576, just over a million. So 21 levels. For 1,000 it is 10 halvings (2¹⁰ is 1,024), so 11 levels. That count of halvings is written log₂ n, and it grows very slowly: double the days and you add one level.

How many boxes can a question look at? On any level the boxes sit side by side with no gaps, and your range is one unbroken stretch. So only two boxes on a level can be cut by it: the one holding its left end and the one holding its right end. Every other box is fully in or fully out, and the walk stops there.

Two split boxes on one level means at most four children to look at on the next. So a question looks at no more than 4 boxes per level, and fewer near the top, where there are only 1 or 2 boxes. You saw this in the days 1–6 walk: 1, then 2, then 4, then 4, for 11 in total.

The same steps as code

To store the tree in a plain array, number the boxes level by level: the root is box 1, level 1 is boxes 2 and 3, level 2 is boxes 4 to 7, and the leaves are 8 to 15. Then box i’s children are always 2i and 2i + 1: box 2 (days 0–3) has children 4 (0–1) and 5 (2–3). Starting at 1 is what makes this work; a root at 0 would have children 0 and 1, itself included.

With uneven halves some numbers are never used, so the array needs more slots than there are boxes. 4n slots is always enough.

Each function below calls itself on a box’s children, so it walks down from the root. When those calls return, the code adds the children’s totals, so the totals are redone from the bottom up, just as you did by hand.

# tree[i] holds the total for days lo..hi. The root is box 1.
build(i, lo, hi):
    if lo == hi:
        tree[i] = bowls[lo]
        return
    mid = (lo + hi) // 2
    build(2*i, lo, mid)
    build(2*i + 1, mid + 1, hi)
    tree[i] = tree[2*i] + tree[2*i + 1]

query(i, lo, hi, l, r):                     # bowls from day l to day r
    if r < lo or hi < l: return 0           # all outside: skip
    if l <= lo and hi <= r: return tree[i]  # all inside: use it
    mid = (lo + hi) // 2                    # partly inside: split
    return query(2*i, lo, mid, l, r) + query(2*i + 1, mid + 1, hi, l, r)

update(i, lo, hi, day, value):
    if lo == hi:
        tree[i] = value
        return
    mid = (lo + hi) // 2
    if day <= mid: update(2*i, lo, mid, day, value)
    else:          update(2*i + 1, mid + 1, hi, day, value)
    tree[i] = tree[2*i] + tree[2*i + 1]     # redo totals on the way back up

Not just totals

A box can store anything you can work out from its two children alone. The busiest day in days 0–3 is the busier of the busiest in 0–1 and the busiest in 2–3. So swap + for max and the same tree answers “how many bowls on the busiest day from day l to day r?”. Switch the demo to Largest and the root shows 20; switch to Smallest and it shows 3.

That gives the number of bowls, not which day it was. To get the day too, store a pair in each box, the bowls and the day, and keep whichever pair has more bowls.

Choosing for the dashboard

There is one more obvious approach, the running total: for each day, store the bowls from day 0 up to that day. For our 8 days that is 12, 19, 39, 44, 53, 67, 70, 88.

Then days l to r is one subtraction: the running total at day r minus the one at day l − 1. Days 1–6 is 70 − 12 = 58. When l is 0 there is nothing to subtract: days 0–r is just the running total at day r. Two reads at most, however long the range.

But change day 3, and every running total from day 3 onwards is now wrong. On a million days, one change can mean a million fixes. Here are all three side by side, for a million days:

• The numbers never change: running totals.
• Questions are rare or ranges are short: just loop.
• Lots of questions and lots of changes, like this live dashboard: a segment tree.
• Only sums, with single-day changes: a Fenwick tree (it has its own article here) does the same job in less code and memory. Pick the segment tree when you need min, max or your own way of combining two halves.

The same shape shows up well beyond ramen: a leaderboard asking “how many players scored between 500 and 900?” while scores change, or a metrics chart asking for the peak in any time window while new points keep arriving.