Data Structures & Algorithms (DSA) Module 19 – Range queries and tree queries
Segment trees: build, query, update
How a segment tree splits an array into halves so that range minimums, maximums or sums with changing values cost O(log n), in recursive and bottom-up form.
What you will learn
- Build a segment tree for sum, minimum or maximum
- Answer range queries and point updates in O(log n)
- Write both the recursive and the bottom-up iterative version
Before you start
What you’ll learn · Before you start
What you will learn
- Build a segment tree for sum, minimum or maximum
- Answer range queries and point updates in O(log n)
- Write both the recursive and the bottom-up iterative version
Before you start
On this page
A segment tree answers range questions on an array whose values change: the minimum, maximum or sum of positions l to r, and a change to one value, each in O(log n). It is a binary tree in which every node covers a range of the array. The root covers all of it, each node’s two children cover the left and right halves of its range, and the leaves cover one position each. Every node stores the answer for its range, combined from its two children. A query takes the nodes that lie entirely inside the asked range, at most two on any level, and an update changes one leaf and the nodes above it. Any associative operation works, such as minimum, maximum, sum, the greatest common divisor or a product of matrices, and that is what a Fenwick tree cannot offer: it needs an operation that subtraction can undo. Bentley and Wood used segment trees in 1980 to report which rectangles intersect.
Nodes, halves and the array behind them
In the recursive layout the root is node 1 and covers positions 0 to n − 1. Node v covers some range lo to hi; with mid = (lo + hi) // 2, its left child, node 2v, covers lo to mid and its right child, node 2v + 1, covers mid + 1 to hi. The nodes live in a list indexed by their numbers, and a list of 4n slots is always large enough. Building fills the leaves and then each node from its children, once per node: O(n) work for about 2n nodes.
Every node holds the maximum of its range; a query takes whole nodes and splits the others
Text description of the diagram
The tree has four levels. The leaves at the bottom hold the eight scores of contestants 0 to 7: 71, 45, 88, 62, 97, 54, 80 and 66. Each node above holds the larger of its two children, and its label gives the range it covers.
- Level 3, the leaves: one contestant each.
- Level 2: 0-1 holds 71, 2-3 holds 88, 4-5 holds 97 and 6-7 holds 80.
- Level 1: 0-3 holds 88 and 4-7 holds 97.
- Level 0, the root: 0-7 holds 97, the best score of all.
The query for contestants 2 to 6 starts at the root. The root, 0-3, 4-7 and 6-7 overlap the range only partly, so the query splits each of them and asks both children; they are drawn with dashed outlines. The nodes 2-3, 4-5 and the leaf 6 lie inside the range, so the query takes their values whole without looking below them; they are drawn with thick outlines. Their values are 88, 97 and 80, and the answer is the largest, 97. Nodes 0-1, 7 and those below the nodes taken whole are not visited.
A query takes whole nodes and splits the rest
A query for the range left to right starts at the root and handles each node in one of three ways:
- No overlap. The node’s range lies outside the query: return the identity of the operation, a value that changes nothing, such as minus infinity for maximum or 0 for sum.
- Inside. The node’s range lies inside the query: return the node’s value without looking below it.
- Partial overlap. Ask both children and combine their answers.
Only the two ends of the range can cut through a node, so on each level the query splits at most two nodes and takes at most two whole, and it visits O(log n) nodes in all. A point update walks from the root to the leaf of its position, changes the leaf, and recomputes every node on the way back up, ⌈log₂ n⌉ + 1 nodes.
A leaderboard, traced
Eight contestants have scores, and the board must show the best score of any range of contestants while scores
change. The program prints which nodes each query takes whole, changes one score, and then checks 1,000 random
changes and queries against max() over a slice:
Python · trace/segment_tree.py
"""The best score in any range of eight contestants (synthetic leaderboard), in a recursive segment tree of maximums."""
import random
NEG_INF = float("-inf") # the identity of max: max(x, NEG_INF) == x
class MaxSegmentTree:
"""Node v covers values[lo .. hi]; its children 2v and 2v + 1 cover the two halves. The root is node 1."""
def __init__(self, values):
self.n = len(values)
self.best = [NEG_INF] * (4 * self.n)
def build(v, lo, hi):
if lo == hi:
self.best[v] = values[lo]
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid + 1, hi)
self.best[v] = max(self.best[2 * v], self.best[2 * v + 1])
build(1, 0, self.n - 1)
def query(self, left, right, used=None):
"""The maximum of values[left .. right]; `used`, if given, collects the ranges of the nodes taken whole."""
def visit(v, lo, hi):
if right < lo or hi < left: # no overlap
return NEG_INF
if left <= lo and hi <= right: # the node lies inside the range: take it whole
if used is not None:
used.append((lo, hi))
return self.best[v]
mid = (lo + hi) // 2 # a partial overlap: ask both children
return max(visit(2 * v, lo, mid), visit(2 * v + 1, mid + 1, hi))
return visit(1, 0, self.n - 1)
def update(self, i, value):
"""values[i] = value: change the leaf, then every node above it on the way back up."""
def visit(v, lo, hi):
if lo == hi:
self.best[v] = value
return
mid = (lo + hi) // 2
if i <= mid:
visit(2 * v, lo, mid)
else:
visit(2 * v + 1, mid + 1, hi)
self.best[v] = max(self.best[2 * v], self.best[2 * v + 1])
visit(1, 0, self.n - 1)
def nodes(used):
return ", ".join(f"{lo}-{hi}" for lo, hi in used)
scores = [71, 45, 88, 62, 97, 54, 80, 66]
tree = MaxSegmentTree(scores)
print("scores of contestants 0-7:", scores)
for left, right in [(2, 6), (0, 3), (5, 7)]:
used = []
best = tree.query(left, right, used)
print(f"best of {left}-{right}: {best}, from the nodes for {nodes(used)}")
tree.update(4, 58)
print("contestant 4 drops to 58")
used = []
print(f"best of 2-6: {tree.query(2, 6, used)}, from the nodes for {nodes(used)}")
rng = random.Random(6)
values = [rng.randint(0, 100) for _ in range(50)]
check = MaxSegmentTree(values)
agree = 0
for _ in range(1000):
i = rng.randrange(50)
values[i] = rng.randint(0, 100)
check.update(i, values[i])
left = rng.randrange(50)
right = rng.randrange(left, 50)
agree += check.query(left, right) == max(values[left : right + 1])
print(f"{agree:,} of 1,000 random updates and queries agree with max() over a slice")Output
scores of contestants 0-7: [71, 45, 88, 62, 97, 54, 80, 66] best of 2-6: 97, from the nodes for 2-3, 4-5, 6-6 best of 0-3: 88, from the nodes for 0-3 best of 5-7: 80, from the nodes for 5-5, 6-7 contestant 4 drops to 58 best of 2-6: 88, from the nodes for 2-3, 4-5, 6-6 1,000 of 1,000 random updates and queries agree with max() over a slice
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 segment_tree.py
JavaScript · trace/segment_tree.mjs
// The best score in any range of eight contestants (synthetic leaderboard), in a recursive segment tree of maximums.
/** Node v covers values[lo .. hi]; its children 2v and 2v + 1 cover the two halves. The root is node 1. */
class MaxSegmentTree {
constructor(values) {
this.n = values.length;
this.best = new Array(4 * this.n).fill(-Infinity); // -Infinity is the identity of max
const build = (v, lo, hi) => {
if (lo === hi) {
this.best[v] = values[lo];
return;
}
const mid = Math.floor((lo + hi) / 2);
build(2 * v, lo, mid);
build(2 * v + 1, mid + 1, hi);
this.best[v] = Math.max(this.best[2 * v], this.best[2 * v + 1]);
};
build(1, 0, this.n - 1);
}
/** The maximum of values[left .. right]; `used`, if given, collects the ranges of the nodes taken whole. */
query(left, right, used = null) {
const visit = (v, lo, hi) => {
if (right < lo || hi < left) return -Infinity; // no overlap
if (left <= lo && hi <= right) {
if (used) used.push([lo, hi]); // the node lies inside the range: take it whole
return this.best[v];
}
const mid = Math.floor((lo + hi) / 2); // a partial overlap: ask both children
return Math.max(visit(2 * v, lo, mid), visit(2 * v + 1, mid + 1, hi));
};
return visit(1, 0, this.n - 1);
}
/** values[i] = value: change the leaf, then every node above it on the way back up. */
update(i, value) {
const visit = (v, lo, hi) => {
if (lo === hi) {
this.best[v] = value;
return;
}
const mid = Math.floor((lo + hi) / 2);
if (i <= mid) visit(2 * v, lo, mid);
else visit(2 * v + 1, mid + 1, hi);
this.best[v] = Math.max(this.best[2 * v], this.best[2 * v + 1]);
};
visit(1, 0, this.n - 1);
}
}
const nodes = (used) => used.map(([lo, hi]) => `${lo}-${hi}`).join(', ');
/** Digits in groups of three, as Python prints them with a comma format. */
const grouped = (v) => String(v).replace(/\B(?=(\d{3})+(?!\d))/g, ',');
const scores = [71, 45, 88, 62, 97, 54, 80, 66];
const tree = new MaxSegmentTree(scores);
console.log(`scores of contestants 0-7: [${scores.join(', ')}]`);
for (const [left, right] of [[2, 6], [0, 3], [5, 7]]) {
const used = [];
const best = tree.query(left, right, used);
console.log(`best of ${left}-${right}: ${best}, from the nodes for ${nodes(used)}`);
}
tree.update(4, 58);
console.log('contestant 4 drops to 58');
const used = [];
console.log(`best of 2-6: ${tree.query(2, 6, used)}, from the nodes for ${nodes(used)}`);
// 1,000 random updates and queries on 50 values, checked against a scan (a seeded generator).
let seed = 6;
const pick = (lo, hi) => {
seed = (seed * 48271) % 2147483647;
return lo + (seed % (hi - lo + 1));
};
const values = Array.from({ length: 50 }, () => pick(0, 100));
const check = new MaxSegmentTree(values);
let agree = 0;
for (let t = 0; t < 1000; t++) {
const i = pick(0, 49);
values[i] = pick(0, 100);
check.update(i, values[i]);
const left = pick(0, 49);
const right = pick(left, 49);
if (check.query(left, right) === Math.max(...values.slice(left, right + 1))) agree++;
}
console.log(`${grouped(agree)} of 1,000 random updates and queries agree with max() over a slice`);Output
scores of contestants 0-7: [71, 45, 88, 62, 97, 54, 80, 66] best of 2-6: 97, from the nodes for 2-3, 4-5, 6-6 best of 0-3: 88, from the nodes for 0-3 best of 5-7: 80, from the nodes for 5-5, 6-7 contestant 4 drops to 58 best of 2-6: 88, from the nodes for 2-3, 4-5, 6-6 1,000 of 1,000 random updates and queries agree with max() over a slice
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node segment_tree.mjs
Runs on this device, in your browser. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
The query for contestants 2 to 6 takes the nodes 2–3, 4–5 and 6 whole, as in the diagram, and returns 97. The query for 0 to 3 is a single node, because the root’s left child covers exactly that range. After contestant 4 drops from 97 to 58, the same query takes the same three nodes, but node 4–5 now holds 58, so the answer is 88.
| Operation | Time | Extra space |
|---|---|---|
| Build | O(n) | O(n) |
| Query a range | O(log n) | O(log n) |
| Change one value | O(log n) | O(log n) |
Other ways to build the same tree
The bottom-up iterative tree keeps the leaves at positions n to 2n − 1 of a list of 2n slots and climbs with i // 2, so it needs no recursion. Any associative combine works, but an operation whose order matters, such as joining strings or multiplying matrices, needs a left and a right accumulator in the iterative query. Richer nodes store several numbers at once, such as the best subarray sum of their range, and harder range questions become one combine step. Descending the tree finds the first position at or after a start whose value reaches a threshold, in O(log n). For sums alone, a Fenwick tree is smaller and simpler.
Exercise and self-check
Answer range minimums while single values change. The sample tests include a list of seven values, which a list of only 2n slots in the recursive layout cannot hold.
Exercise · Medium · Python, JavaScript
Range minimums while single values change
Write run_operations(values, operations) (JavaScript: runOperations) for a list of integers that changes over time. Each operation is one of:
("set", i, x)(JavaScript:["set", i, x]): from now onvalues[i]isx;("min", left, right): the smallest ofvalues[left]tovalues[right], both ends included.
Positions count from 0. Return the answers of the "min" operations, in order. The sample tests check the scores of the lesson, single values, negative numbers and repeated changes of one position, compare your answers with a slice on random cases, and include a list of 7 values, where a tree with too few slots fails.
Python · Starter code · minimums.py
def run_operations(values, operations):
"""Answers of the ("min", left, right) operations, in order; ("set", i, x) changes one value."""
raise NotImplementedError("write run_operations")The sample tests · test_minimums.py
import random
from minimums import run_operations
SCORES = [71, 45, 88, 62, 97, 54, 80, 66]
def slow(values, operations):
values = list(values)
out = []
for op, a, b in operations:
if op == "set":
values[a] = b
else:
out.append(min(values[a : b + 1]))
return out
def test_scores_of_the_lesson():
"""the eight scores of the lesson, before and after a change"""
ops = [("min", 2, 6), ("set", 5, 90), ("min", 2, 6), ("min", 0, 7), ("min", 7, 7)]
assert run_operations(SCORES, ops) == [54, 62, 45, 66]
def test_single_value():
"""a list of one value, changed and asked"""
assert run_operations([5], [("min", 0, 0), ("set", 0, -2), ("min", 0, 0)]) == [5, -2]
def test_negative_values_and_repeated_changes():
"""negative values and the same position changed again and again"""
ops = [("set", 3, -9), ("min", 0, 4), ("set", 3, 10), ("min", 0, 4), ("set", 3, 1), ("min", 3, 3)]
assert run_operations([4, -1, 6, 2, 8], ops) == [-9, -1, 1]
def test_seven_values():
"""seven values: every position changed and every range asked"""
values = [9, 4, 7, 1, 8, 3, 6]
ops = [("set", i, 20 - i) for i in range(7)] + [("min", l, r) for l in range(7) for r in range(l, 7)]
assert run_operations(values, ops) == slow(values, ops)
def test_random_against_slices():
"""300 random cases, compared with min() over a slice"""
rng = random.Random(10)
for _ in range(300):
n = rng.randint(1, 25)
values = [rng.randint(-50, 50) for _ in range(n)]
ops = []
for _ in range(rng.randint(1, 40)):
if rng.random() < 0.5:
ops.append(("set", rng.randrange(n), rng.randint(-50, 50)))
else:
left = rng.randrange(n)
ops.append(("min", left, rng.randrange(left, n)))
assert run_operations(values, ops) == slow(values, ops), (values, ops)JavaScript · Starter code · minimums.mjs
/** Answers of the ["min", left, right] operations, in order; ["set", i, x] changes one value. */
export function runOperations(values, operations) {
throw new Error('write runOperations');
}The sample tests · minimums.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { runOperations } from './minimums.mjs';
const SCORES = [71, 45, 88, 62, 97, 54, 80, 66];
function slow(values, operations) {
const v = values.slice();
const out = [];
for (const [op, a, b] of operations) {
if (op === 'set') v[a] = b;
else out.push(Math.min(...v.slice(a, b + 1)));
}
return out;
}
/** A seeded generator (Park and Miller), so every run checks the same cases. */
function generator(seed) {
let s = seed;
return (lo, hi) => {
s = (s * 48271) % 2147483647;
return lo + (s % (hi - lo + 1));
};
}
test('the eight scores of the lesson, before and after a change', () => {
const ops = [['min', 2, 6], ['set', 5, 90], ['min', 2, 6], ['min', 0, 7], ['min', 7, 7]];
assert.deepEqual(runOperations(SCORES, ops), [54, 62, 45, 66]);
});
test('a list of one value, changed and asked', () => {
assert.deepEqual(runOperations([5], [['min', 0, 0], ['set', 0, -2], ['min', 0, 0]]), [5, -2]);
});
test('negative values and the same position changed again and again', () => {
const ops = [['set', 3, -9], ['min', 0, 4], ['set', 3, 10], ['min', 0, 4], ['set', 3, 1], ['min', 3, 3]];
assert.deepEqual(runOperations([4, -1, 6, 2, 8], ops), [-9, -1, 1]);
});
test('seven values: every position changed and every range asked', () => {
const values = [9, 4, 7, 1, 8, 3, 6];
const ops = [];
for (let i = 0; i < 7; i++) ops.push(['set', i, 20 - i]);
for (let l = 0; l < 7; l++) for (let r = l; r < 7; r++) ops.push(['min', l, r]);
assert.deepEqual(runOperations(values, ops), slow(values, ops));
});
test('300 random cases, compared with a scan of each range', () => {
const pick = generator(10);
for (let t = 0; t < 300; t++) {
const n = pick(1, 25);
const values = Array.from({ length: n }, () => pick(-50, 50));
const ops = [];
for (let j = 0, m = pick(1, 40); j < m; j++) {
if (pick(0, 1) === 0) ops.push(['set', pick(0, n - 1), pick(-50, 50)]);
else {
const left = pick(0, n - 1);
ops.push(['min', left, pick(left, n - 1)]);
}
}
assert.deepEqual(runOperations(values, ops), slow(values, ops), JSON.stringify([values, ops]));
}
});A hint
The bottom-up tree is the shortest version: a list of 2 * n slots with the values at n to 2n - 1 and tree[i] = min(tree[2i], tree[2i + 1]) above them. A change sets its leaf and recomputes i // 2 up to the root; a query climbs from both ends of the half-open range [left + n, right + 1 + n).
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Why a query is O(log n) and why 4n slots suffice: the proofs, with nodes counted Pro: opens with a Pro, Premium or Ultimate pass
Two bounds hold every segment tree together: how many nodes a query visits and how many slots the recursive layout needs. This part proves both and checks them on 100,000 random queries and on every size up to 100,000.
In this part:
- At most four nodes per level: the proof
- Why 4n slots are enough, and 2n are not
- Nodes visited and slots used, measured
1 runnable example (Python) · about 2 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
The bottom-up tree in 2n slots, kept in order and timed against recursion Pro: opens with a Pro, Premium or Ultimate pass
The bottom-up tree drops the recursion and half of the memory. This part writes it, shows the one change that keeps non-commutative operations in order, and times both trees on 200,000 operations.
In this part:
- Leaves at n to 2n − 1, and a climb from both ends
- Two accumulators keep the order of operations that do not commute
- Recursive against bottom-up on 200,000 operations, measured
2 runnable examples (Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Richer nodes, five languages and four bugs reproduced Pro: opens with a Pro, Premium or Ultimate pass
A node can carry more than one number, which turns harder range questions into the same climb. This part builds a tree for the best subarray sum of any range and a descent to the first value above a bar, runs one program in five languages and reproduces four bugs that pass quick tests.
In this part:
- The best run of a range: four numbers per node, worked
- A tree of minimums in five languages, run and recorded
- Four bugs that pass a quick test, reproduced
- Edge cases worth a test
4 runnable examples (C++, Go, Java, JavaScript, Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher to mid · Warm-up
When do you need a segment tree rather than a Fenwick tree?
When the operation cannot be undone. A Fenwick tree answers a range as the difference of two prefix results, which works for sums because subtraction undoes addition, but nothing undoes a minimum, a maximum or a greatest common divisor. A segment tree combines whole nodes instead, so any associative operation works, including ones whose order matters, such as joining strings or multiplying matrices. It also wins when a node must hold several values at once, such as the best subarray sum of its range. For plain sums with point updates, the Fenwick tree is smaller, with n + 1 numbers instead of 2n to 4n, and its loops are shorter, so choose it there.
-
Mid to senior
An analytics page shows the highest fare in any range of the last 1,000,000 trips. Fares are corrected after disputes a few thousand times a minute, and 20,000 range questions arrive every second. Which structure do you choose, how much memory does it take, and what does each operation cost?
-
Mid to senior
A dashboard needs both the total and the maximum of any range of 500,000 sensor readings that keep changing. A colleague proposes a Fenwick tree for the totals and a separate segment tree for the maximums. What would you build instead, and what does your design save?
-
Fresher to mid
A teammate changed mid = (lo + hi) // 2 to mid = (lo + hi + 1) // 2 in a recursive segment tree "to balance the halves". Now every input with more than one value crashes with RecursionError. Explain exactly why, and what a version that rounds up must change.
Key takeaways
- A segment tree stores, for every node, the combined value of a range; children cover the two halves of their parent’s range.
- A query takes whole nodes and splits the others, at most two of each per level, so it costs O(log n).
- A point update changes a leaf and every node above it, ⌈log₂ n⌉ + 1 nodes.
- The identity value, the 4n slots of the recursive layout and the split at mid are where most bugs live.
- Prefer a Fenwick tree for sums alone; use a segment tree for minimum, maximum and any other associative operation.
References
- An optimal worst case algorithm for reporting intersections of rectangles (J. L. Bentley and D. Wood, IEEE Transactions on Computers C-29(7), 1980) (IEEE)
- A new data structure for cumulative frequency tables (P. M. Fenwick, Software: Practice and Experience 24(3), 1994) (John Wiley & Sons)
- Dictionary of Algorithms and Data Structures: associative (National Institute of Standards and Technology (NIST))
- Dictionary of Algorithms and Data Structures: complete binary tree (National Institute of Standards and Technology (NIST))
- sys.setrecursionlimit (The Python Standard Library) (Python Software Foundation)
- functools.cache (The Python Standard Library) (Python Software Foundation)
- ECMAScript language specification: TypedArray objects (Ecma International (TC39))
- ACM/IEEE-CS/AAAI Computer Science Curricula 2023: Algorithmic Foundations (AL) (ACM, IEEE Computer Society and AAAI)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress