SyntaxPilot
Courses/DSA and Coding Problems/Lesson 82
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 82 of 90

Segment tree: range sum with point updates

queued

These are the notes for DSA episode 82. A kirana shop keeps one line of sales per day; the accountant keeps asking for the total from day l to day r, and the owner keeps correcting single days. We try the obvious way, adding up the range every time (correct, then Time Limit Exceeded on a million days and a million operations), then prefix sums from episode 2 (fast questions, but every correction rewrites up to n totals: Time Limit Exceeded again). The fix is to store the sums of halves of halves: a segment tree, where a query glues together a few whole blocks and an update fixes one path to the root, both in O(log n). Then three real bugs: a 2n tree array, a forgotten recompute, and int sums. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The shop In code
The sales ledger, one line per day the array a, length n
"Total sales from day 40 to day 300?" sumRange(40, 300)
"Day 120 was wrong, it should be 950" update(120, 950)
Weekly and monthly totals kept by a good accountant the boxes of the segment tree
Fixing a day also fixes its week, month and year totals an update walks one path to the root

Every word, from zero

  • Array: numbers stored side by side, reached by index 0 .. n − 1.
  • Range query: a question about a contiguous part a[l..r] of an array (here: its sum).
  • Point update: changing one element, a[i] = v.
  • Mutable: can change after it is built (the opposite of static or immutable).
  • Prefix sum: pre[k] = a[0] + … + a[k − 1]; then sum(l..r) = pre[r + 1] − pre[l] (episode 2).
  • Block / segment: a contiguous range [lo..hi] of the array.
  • Tree: boxes (nodes) connected parent to children, with one box at the top, the root.
  • Leaf: a box with no children; in a segment tree, one array element.
  • Binary tree: every box has at most two children, left and right.
  • Segment tree: a binary tree where each box stores the sum (or min, max, …) of one block, and its children split that block in half.
  • Heap numbering: store the boxes in an array: the root is 1, the children of box k are 2k and 2k + 1.
  • Overlap: two ranges share at least one index.
  • Recursion: a method that calls itself on a smaller part of the problem.
  • log₂ n: how many times you can halve n before reaching 1 (about 20 for a million).
  • Overflow: an int result past 2³¹ − 1 (about 2.1 billion) wraps around to a wrong, often negative, number.
  • Checksum: one number combining many answers, used to compare two programs quickly.

Problem statement

Implement a class with:

  • NumArray(long[] a): build from the array,
  • void update(int i, long v): set a[i] = v,
  • long sumRange(int l, int r): return a[l] + a[l + 1] + … + a[r] (both ends included).

n and the number of operations can each be up to a million (LeetCode 307 uses 3 × 10⁴ of each).

Operations on a = 5 3 7 2 6 1 4 8 Answer Why
sumRange(2, 6) 20 7 + 2 + 6 + 1 + 4
update(3, 10), then sumRange(2, 6) 28 the 2 became 10: +8
sumRange(0, 7) 44 36 + 8
sumRange(4, 4) 6 a range of one element
NumArray([42]).sumRange(0, 0) 42 an array of one element

Obvious idea: add up the range every time

update just writes the value; sumRange loops from l to r.

import java.util.*;

public class Main {
    static class NumArray {
        long[] a;
        NumArray(long[] a) { this.a = a.clone(); }
        void update(int i, long v) { a[i] = v; }
        long sumRange(int l, int r) {
            long sum = 0;
            for (int k = l; k <= r; k++) sum += a[k];
            return sum;
        }
    }
    public static void main(String[] args) {
        NumArray s = new NumArray(new long[]{5, 3, 7, 2, 6, 1, 4, 8});
        System.out.println(s.sumRange(2, 6));
        s.update(3, 10);
        System.out.println(s.sumRange(2, 6));
        System.out.println(s.sumRange(0, 7));
        System.out.println(s.sumRange(4, 4));
        NumArray one = new NumArray(new long[]{42});
        System.out.println(one.sumRange(0, 0));
    }
}

Output (real):

20
28
44
6
42

The big test

A million days (a[i] = i % 100) and a million operations from new Random(42): even ones are updates, odd ones are queries on random ranges. We print a checksum of all query answers and the time.

        int n = 1_000_000;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = i % 100;
        NumArray s = new NumArray(a);
        Random rnd = new Random(42);
        long check = 0, t0 = System.nanoTime();
        for (int q = 0; q < 1_000_000; q++) {
            int i = rnd.nextInt(n), j = rnd.nextInt(n);
            if (q % 2 == 0) s.update(i, j % 100);
            else check += s.sumRange(Math.min(i, j), Math.max(i, j));
        }
        System.out.println(check + ", " + (System.nanoTime() - t0) / 1000000 + " ms");

Result with the add-it-up version: Time Limit Exceeded (25 s).

Why is it slow?

update sumRange
Plain array O(1) O(n): up to n additions

Half a million queries on random ranges add about a third of a million numbers each: around 10¹¹ additions. Every query re-adds numbers that earlier queries already added.

Fix 1: prefix sums (fast questions, slow corrections)

import java.util.*;

public class Main {
    static class NumArray {
        long[] a, pre;
        NumArray(long[] a) {
            this.a = a.clone();
            pre = new long[a.length + 1];
            for (int k = 0; k < a.length; k++) pre[k + 1] = pre[k] + a[k];
        }
        void update(int i, long v) {
            long diff = v - a[i];
            a[i] = v;
            for (int k = i + 1; k < pre.length; k++) pre[k] += diff;
        }
        long sumRange(int l, int r) { return pre[r + 1] - pre[l]; }
    }
    public static void main(String[] args) {
        NumArray s = new NumArray(new long[]{5, 3, 7, 2, 6, 1, 4, 8});
        System.out.println(s.sumRange(2, 6));
        s.update(3, 10);
        System.out.println(s.sumRange(2, 6));
        System.out.println(s.sumRange(0, 7));
        System.out.println(s.sumRange(4, 4));
        NumArray one = new NumArray(new long[]{42});
        System.out.println(one.sumRange(0, 0));
    }
}

Output (real):

20
28
44
6
42

On the big test: Time Limit Exceeded again. Now sumRange is one subtraction, but update(i) must fix pre[i + 1], pre[i + 2], …, pre[n]: about half a million prefixes per update.

update sumRange
Plain array O(1) O(n)
Prefix sums O(n) O(1)

One side is always O(n): a single day belongs to one box in the plain array (so queries need many boxes), but to n − i prefixes (so updates touch many boxes). We want something in between.

The key insight: store sums of halves of halves

Keep totals like an accountant keeps daily, weekly and monthly totals. Split the array in half, each half in half, and so on down to single days, and store the sum of every block. Each block's sum is its left half plus its right half.

For a = 5 3 7 2 6 1 4 8:

                         [0..7] = 36
              [0..3] = 17              [4..7] = 19
        [0..1] = 8   [2..3] = 9   [4..5] = 7   [6..7] = 12
       5     3      7     2      6     1      4     8
  • Query sumRange(2, 6): [2..3] = 9, [4..5] = 7 and a[6] = 4: three boxes, 20.
  • Update a[3] = 10 (+8): only a[3], [2..3], [0..3] and the root change: one box per level.

Every day sits in exactly one box per level, and there are about log₂ n levels (20 for a million). A query uses at most two whole boxes per level (it visits at most four), and an update fixes one box per level.

Storing it in an array

Box Covers Children
1 (root) [0..n − 1] 2, 3
k [lo..hi], mid = (lo + hi) / 2 2k covers [lo..mid], 2k + 1 covers [mid + 1..hi]

When n is not a power of two the tree is lopsided and the heap numbers leave gaps, so the array needs up to 4n slots (2n is not enough: see bug 1).

The three cases of a query

Box [lo..hi] vs the query [l..r] Return
no overlap: r < lo or hi < l 0
fully inside: l <= lo and hi <= r t[k]
partly inside query(left child) + query(right child)

Solution in Java: the segment tree

import java.util.*;

public class Main {
    static class NumArray {
        int n;
        long[] t;
        NumArray(long[] a) {
            n = a.length;
            t = new long[4 * n];
            build(a, 1, 0, n - 1);
        }
        void build(long[] a, int node, int lo, int hi) {
            if (lo == hi) { t[node] = a[lo]; return; }
            int mid = (lo + hi) / 2;
            build(a, 2 * node, lo, mid);
            build(a, 2 * node + 1, mid + 1, hi);
            t[node] = t[2 * node] + t[2 * node + 1];
        }
        long query(int node, int lo, int hi, int l, int r) {
            if (r < lo || hi < l) return 0;
            if (l <= lo && hi <= r) return t[node];
            int mid = (lo + hi) / 2;
            return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
        }
        void set(int node, int lo, int hi, int i, long v) {
            if (lo == hi) { t[node] = v; return; }
            int mid = (lo + hi) / 2;
            if (i <= mid) set(2 * node, lo, mid, i, v);
            else set(2 * node + 1, mid + 1, hi, i, v);
            t[node] = t[2 * node] + t[2 * node + 1];
        }
        long sumRange(int l, int r) { return query(1, 0, n - 1, l, r); }
        void update(int i, long v) { set(1, 0, n - 1, i, v); }
    }
    public static void main(String[] args) {
        NumArray s = new NumArray(new long[]{5, 3, 7, 2, 6, 1, 4, 8});
        System.out.println(s.sumRange(2, 6));
        s.update(3, 10);
        System.out.println(s.sumRange(2, 6));
        System.out.println(s.sumRange(0, 7));
        System.out.println(s.sumRange(4, 4));
        NumArray one = new NumArray(new long[]{42});
        System.out.println(one.sumRange(0, 0));
    }
}

Output (real):

20
28
44
6
42

On the big test: 8257371328477, 369 ms, where both earlier versions timed out.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct NumArray {
    int n;
    vector<long long> t;
    NumArray(const vector<long long>& a) : n(a.size()), t(4 * a.size()) { build(a, 1, 0, n - 1); }
    void build(const vector<long long>& a, int node, int lo, int hi) {
        if (lo == hi) { t[node] = a[lo]; return; }
        int mid = (lo + hi) / 2;
        build(a, 2 * node, lo, mid);
        build(a, 2 * node + 1, mid + 1, hi);
        t[node] = t[2 * node] + t[2 * node + 1];
    }
    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t[node];
        int mid = (lo + hi) / 2;
        return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
    }
    void set(int node, int lo, int hi, int i, long long v) {
        if (lo == hi) { t[node] = v; return; }
        int mid = (lo + hi) / 2;
        if (i <= mid) set(2 * node, lo, mid, i, v);
        else set(2 * node + 1, mid + 1, hi, i, v);
        t[node] = t[2 * node] + t[2 * node + 1];
    }
    long long sumRange(int l, int r) { return query(1, 0, n - 1, l, r); }
    void update(int i, long long v) { set(1, 0, n - 1, i, v); }
};

int main() {
    NumArray s({5, 3, 7, 2, 6, 1, 4, 8});
    cout << s.sumRange(2, 6) << "\n";
    s.update(3, 10);
    cout << s.sumRange(2, 6) << "\n";
    cout << s.sumRange(0, 7) << "\n";
    cout << s.sumRange(4, 4) << "\n";
    NumArray one({42});
    cout << one.sumRange(0, 0) << "\n";
}

Output (real):

20
28
44
6
42

The same solution in Python

class NumArray:
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (4 * self.n)
        self._build(a, 1, 0, self.n - 1)

    def _build(self, a, node, lo, hi):
        if lo == hi:
            self.t[node] = a[lo]
            return
        mid = (lo + hi) // 2
        self._build(a, 2 * node, lo, mid)
        self._build(a, 2 * node + 1, mid + 1, hi)
        self.t[node] = self.t[2 * node] + self.t[2 * node + 1]

    def _query(self, node, lo, hi, l, r):
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.t[node]
        mid = (lo + hi) // 2
        return self._query(2 * node, lo, mid, l, r) + self._query(2 * node + 1, mid + 1, hi, l, r)

    def _set(self, node, lo, hi, i, v):
        if lo == hi:
            self.t[node] = v
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._set(2 * node, lo, mid, i, v)
        else:
            self._set(2 * node + 1, mid + 1, hi, i, v)
        self.t[node] = self.t[2 * node] + self.t[2 * node + 1]

    def sumRange(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def update(self, i, v):
        self._set(1, 0, self.n - 1, i, v)


s = NumArray([5, 3, 7, 2, 6, 1, 4, 8])
print(s.sumRange(2, 6))
s.update(3, 10)
print(s.sumRange(2, 6))
print(s.sumRange(0, 7))
print(s.sumRange(4, 4))
print(NumArray([42]).sumRange(0, 0))

Output (real):

20
28
44
6
42

Three real bugs

Bug 1: a tree array of 2n

A tree with n leaves has 2n − 1 boxes, so 2n looks like enough. With heap numbering and n = 6 it is not:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 12
    at Main$NumArray.build(Main.java:13)
    at Main$NumArray.build(Main.java:15)
    at Main$NumArray.build(Main.java:15)
    at Main$NumArray.build(Main.java:16)
    at Main$NumArray.<init>(Main.java:10)
    at Main.main(Main.java:36)

The lopsided tree uses box numbers up to 12 (and more for other sizes). Use new long[4 * n].

Bug 2: forgot to recompute the box on the way up

set changes the leaf, but without t[node] = t[2 * node] + t[2 * node + 1]; the boxes above it keep their old sums. On the example (20, 28, 44 expected):

20
20
36

Bug 3: int sums

200,000 days of 20,000 each is 4,000,000,000, more than an int can hold:

-294967296

Store sums in long.

Complexity

Approach update sumRange Build Space Big test (10⁶ days, 10⁶ ops)
Plain array O(1) O(n) O(n) O(n) Time Limit Exceeded
Prefix sums O(n) O(1) O(n) O(n) Time Limit Exceeded
Segment tree O(log n) O(log n) O(n) O(n) (4n longs) 369 ms
Fenwick tree (episode 83) O(log n) O(log n) O(n log n) or O(n) O(n) similar, shorter code

Common mistakes

Mistake What you see (real) Why Fix
new long[2 * n] ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 12 heap numbering leaves gaps new long[4 * n]
No recompute after set 20 instead of 28 parents keep old sums t[node] = t[2*node] + t[2*node+1] on the way up
int[] t -294967296 instead of 4000000000 overflow past 2.1 billion long[] t
r < lo && hi < l for "no overlap" StackOverflowError (the recursion never stops at a leaf outside the range) a box can be left or right of the range r < lo \|\| hi < l
mid = (lo + hi) / 2 with huge indices in C++ int negative mid overflow lo + (hi - lo) / 2
Starting the root at index 0 children 0 and 1 collide with the root 2 × 0 = 0 root at 1 (or children 2k + 1, 2k + 2)

Mini project: the shop dashboard

Read a CSV of daily sales (one number per line), build a segment tree, and answer commands from the keyboard: sum 40 300, set 120 950, max 0 364 (keep a second tree with Math.max). Print each answer and how many boxes the query visited.

Practice

1. Range Sum Query - Mutable (LeetCode 307). Today's code, unchanged.

2. Range maximum with updates. Change + to Math.max, and the "no overlap" answer from 0 to Long.MIN_VALUE.

3. How many boxes can one query visit when n = 16? Count them for every range.

4. A bottom-up segment tree in a 2n array. Leaves at n .. 2n − 1, box k = box 2k + box 2k + 1, no recursion.

Solutions
import java.util.*;

public class Main {
    // 2. Range maximum with point updates: the same tree, with max instead of +.
    static class MaxTree {
        int n; long[] t;
        MaxTree(long[] a) { n = a.length; t = new long[4 * n]; build(a, 1, 0, n - 1); }
        void build(long[] a, int k, int lo, int hi) {
            if (lo == hi) { t[k] = a[lo]; return; }
            int mid = (lo + hi) / 2;
            build(a, 2 * k, lo, mid); build(a, 2 * k + 1, mid + 1, hi);
            t[k] = Math.max(t[2 * k], t[2 * k + 1]);
        }
        long query(int k, int lo, int hi, int l, int r) {
            if (r < lo || hi < l) return Long.MIN_VALUE;          // the "neutral" value for max
            if (l <= lo && hi <= r) return t[k];
            int mid = (lo + hi) / 2;
            return Math.max(query(2 * k, lo, mid, l, r), query(2 * k + 1, mid + 1, hi, l, r));
        }
        void set(int k, int lo, int hi, int i, long v) {
            if (lo == hi) { t[k] = v; return; }
            int mid = (lo + hi) / 2;
            if (i <= mid) set(2 * k, lo, mid, i, v); else set(2 * k + 1, mid + 1, hi, i, v);
            t[k] = Math.max(t[2 * k], t[2 * k + 1]);
        }
    }
    // 3. Count the boxes a query visits.
    static int visits;
    static long[] t16 = new long[64];
    static long countQuery(int k, int lo, int hi, int l, int r) {
        visits++;
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t16[k];
        int mid = (lo + hi) / 2;
        return countQuery(2 * k, lo, mid, l, r) + countQuery(2 * k + 1, mid + 1, hi, l, r);
    }
    // 4. Bottom-up segment tree in a 2n array: leaves at n..2n-1, box k = box 2k + box 2k+1.
    static class BottomUp {
        int n; long[] t;
        BottomUp(long[] a) {
            n = a.length; t = new long[2 * n];
            for (int i = 0; i < n; i++) t[n + i] = a[i];
            for (int k = n - 1; k >= 1; k--) t[k] = t[2 * k] + t[2 * k + 1];
        }
        void update(int i, long v) {
            for (t[i += n] = v; i > 1; i /= 2) t[i / 2] = t[i] + t[i ^ 1];
        }
        long sumRange(int l, int r) {            // inclusive l..r
            long s = 0;
            for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
                if ((l & 1) == 1) s += t[l++];
                if ((r & 1) == 1) s += t[--r];
            }
            return s;
        }
    }
    public static void main(String[] args) {
        MaxTree mt = new MaxTree(new long[]{5, 3, 7, 2, 6, 1, 4, 8});
        System.out.println(mt.query(1, 0, 7, 2, 6));
        mt.set(1, 0, 7, 3, 10);
        System.out.println(mt.query(1, 0, 7, 2, 6));
        int worst = 0;
        for (int l = 0; l < 16; l++)
            for (int r = l; r < 16; r++) { visits = 0; countQuery(1, 0, 15, l, r); worst = Math.max(worst, visits); }
        System.out.println("most boxes visited for n = 16: " + worst);
        BottomUp b = new BottomUp(new long[]{5, 3, 7, 2, 6, 1});
        System.out.println(b.sumRange(2, 4) + " " + b.sumRange(0, 5));
        b.update(3, 10);
        System.out.println(b.sumRange(2, 4) + " " + b.sumRange(0, 5));
    }
}

Output (real):

7
10
most boxes visited for n = 16: 15
15 24
23 32

The bottom-up version uses only 2n slots because it numbers the leaves first (the recursive version numbers from the root, which leaves gaps).

Quick quiz

In the tree for 5 3 7 2 6 1 4 8, which boxes answer sumRange(0, 5)? A) [0..3] and [4..5] B) [0..7] only C) [0..5] directly D) all six leaves

Answer

A. [0..3] = 17 and [4..5] = 7 are fully inside the range: 17 + 7 = 24. There is no box [0..5].

Interview questions

  1. Why not prefix sums when values change? One update changes every later prefix: O(n) per update.
  2. What does each box of a segment tree store? The sum (or min, max, gcd, …) of its block; its children split the block in half.
  3. Why is a query O(log n)? On each level at most two boxes are partly inside the range, so at most four boxes are visited per level.
  4. Why 4n slots? With heap numbering a lopsided tree leaves unused numbers; 4n is always enough.
  5. Which operations can a segment tree combine? Any associative one with a neutral value: sum (0), min (+∞), max (−∞), gcd (0), product (1).
  6. Segment tree or Fenwick tree? Fenwick is shorter for prefix-style sums; a segment tree handles min/max, arbitrary ranges and, with lazy propagation, range updates.
  7. How would you add 5 to every element of a range? Lazy propagation: store pending additions in boxes and push them down only when needed.

Glossary

Term Meaning
Range query A question about a[l..r], such as its sum
Point update Changing one element a[i] = v
Mutable Can change after it is built
Prefix sum pre[k] = sum of the first k elements
Block / segment A contiguous range [lo..hi]
Tree / root / leaf Boxes linked parent to child; the top box; a box with no children
Segment tree Each box stores its block's sum; children split the block in half
Heap numbering Root 1, children of k are 2k and 2k + 1
Overlap Two ranges share an index
Recursion A method that calls itself on a smaller part
log₂ n How many halvings until 1 (about 20 for a million)
Overflow An int past 2³¹ − 1 wraps to a wrong value
Checksum One number combining many answers
Lazy propagation Postponing range updates inside a segment tree

Summary

  • Adding up the range is O(n) per query; prefix sums make the query O(1) but the update O(n). A mixed million operations times out either way.
  • A segment tree stores the sum of every block of halves of halves; box k has children 2k and 2k + 1, in an array of 4n longs.
  • Query: no overlap → 0, fully inside → the stored sum, partly → ask both children. Update: change the leaf and recompute the path back to the root.
  • Both are O(log n); the big test runs in about a third of a second.
  • Remember 4n, recompute on the way up, and use long.
  • Next episode: Fenwick tree: count of smaller numbers after self (hard).