Home/Trees/Segment tree
Search algorithmsCTRL K

Segment tree

· range sums with point updates
/trees/segment-tree
NODES
1
about 2n
VISITS
0
nodes touched by this operation
OPERATION
build
running now
ANSWER
—
of the current query
LEAVES
8
one per array value
currentpartly inside: recursefully inside: taken wholerecomputed
n = 8 · seed 7 · 36 steps
step 0 / 35
Values8
segment_tree.ts
1
function build(values: number[], node: number, left: number, right: number) {
2
  if (left === right) {
3
    sums[node] = values[left]; return;
4
  }
5
  const middle = (left + right) >> 1;
6
  build(values, 2 * node, left, middle); build(values, 2 * node + 1, middle + 1, right); sums[node] = sums[2 * node] + sums[2 * node + 1];
7
}
8
function query(node: number, left: number, right: number, from: number, to: number): number {
9
  // the sum of values[from..to], visiting only the nodes that straddle the ends
10
  if (to < left || right < from) return 0;
11
  if (from <= left && right <= to) return sums[node];
12
  const middle = (left + right) >> 1;
13
  return query(2 * node, left, middle, from, to) + query(2 * node + 1, middle + 1, right, from, to);
14
}
15
function update(node: number, left: number, right: number, index: number, value: number) {
16
  if (left === right) { sums[node] = value; return; }
17
  const middle = (left + right) >> 1; if (index <= middle) update(2 * node, left, middle, index, value); else update(2 * node + 1, middle + 1, right, index, value);
18
  sums[node] = sums[2 * node] + sums[2 * node + 1];
19
}
CURRENT STEP
line 5

Node [0, 7] splits at 3: build [0, 3] and [4, 7] first.

// how it works

Understanding Segment tree

segment tree · every node owns a range, every query touches only the ranges that straddle its ends
01

The idea

A segment tree puts the array at the leaves and gives every internal node the sum of its two children, so the root holds the total and each node owns a contiguous range. A range query starts at the root: a node fully inside the range contributes its sum in one step, a node fully outside contributes nothing, and only the nodes that straddle an end of the range recurse into their children.

At most two nodes per level straddle, so a query visits O(log n) nodes. A point update changes one leaf and recomputes the log n ancestors above it. Any associative operation works in place of the sum: minimum, maximum, gcd, or a matrix product.

02

The four stages

1
buildleaves are the values, parents the sums
2
insidea node fully inside the query is taken whole
3
straddlea node that crosses an end recurses
4
updateone leaf, then its ancestors
03

Complexity

best
O(1)the query is the whole array: the root answers
average
O(log n)per query and per update
worst
O(log n)at most 4 log n nodes visited
space
O(n)about 2n nodes, 4n in the array layout
04

Versus its siblings

OPERATIONS PER QUERY + UPDATE · 1 000 000 VALUES
segment tree
20
fenwick
20
sqrt decomposition
2,000
prefix sums (query)
1
plain array (update)
1
prefix sums answer in 1 but rebuild in n on every update; a plain array is the opposite
05

Pseudocode

BUILD(node, left, right): a leaf holds its value; otherwise build both halves and store their sum
QUERY(node, left, right, from, to)
  outside the query: 0 · fully inside: the node's sum · straddling: QUERY(left child) + QUERY(right child)
UPDATE(node, left, right, index, value): descend to the leaf, set it, recompute the sums on the way back up
06

When to use

Range queries mixed with updates: leaderboards, time-series windows, computational geometry sweeps, competitive programming's favourite tool.
Any associative combine, and with lazy propagation, range updates too.
07

Pitfalls

The array layout needs 4n slots when n is not a power of two, or an index runs off the end.
Range updates need lazy propagation; updating every leaf in the range is O(n).
Fenwick does prefix sums in less memory and less code; use it when the operation is invertible.
08

History

Jon Bentley introduced segment trees in 1977 for computational geometry, to count intersections of rectangles in a sweep line. The competitive-programming form with an implicit array, lazy propagation and arbitrary monoids grew out of the 2000s contest scene and is now the standard teaching example of a divide-and-conquer data structure.

Back to Trees