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]; thensum(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 boxkare2kand2k + 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
nbefore reaching 1 (about 20 for a million). - Overflow: an
intresult past2³¹ − 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): seta[i] = v,long sumRange(int l, int r): returna[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] = 7anda[6] = 4: three boxes, 20. - Update
a[3] = 10(+8): onlya[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
- Why not prefix sums when values change? One update changes every later prefix: O(n) per update.
- 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.
- 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.
- Why 4n slots? With heap numbering a lopsided tree leaves unused numbers; 4n is always enough.
- Which operations can a segment tree combine? Any associative one with a neutral value: sum (0), min (+∞), max (−∞), gcd (0), product (1).
- 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.
- 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
khas children2kand2k + 1, in an array of4nlongs. - 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 uselong. - Next episode: Fenwick tree: count of smaller numbers after self (hard).