Segment tree

Overview

A segment tree is a binary tree over array ranges. The root covers [0, n - 1], each node covers a range and stores an aggregate of it (sum, min, max, gcd), and each leaf covers one element. Any range query is answered by combining O(log n) nodes, and updating one element changes only the O(log n) nodes on its path to the root.

It is the go-to structure when an array receives both updates and range queries mixed together, where prefix sums (O(n) per update) fail. With lazy propagation, it also supports range updates like 'add 5 to every element in [l, r]' in O(log n).

When to use it

• Range sum / min / max / gcd queries with point updates interleaved.
• Range updates and range queries together (lazy propagation).
• Counting problems after coordinate compression (count smaller elements).
• Any associative combine operation over ranges.

Problem patterns it solves

Where it is used in real software

Key terms

Node range

[start, end] of the array covered by a node.

Merge function

Associative operation combining children: sum, min, max, gcd.

Identity

Neutral value for the merge: 0 for sum, Infinity for min.

Lazy propagation

Store pending range updates at a node and push them to children only when needed.

4n array

An array of size 4n is always large enough for a recursive segment tree.

Query [l, r] recursively

1. 1
   No overlap

   If the node's range is outside [l, r], return the identity (0 for sum).

2. 2
   Full overlap

   If the node's range is inside [l, r], return the node's stored value.

3. 3
   Partial overlap

   Query both children and merge their results.

4. 4
   Point update

   Recurse into the child containing the index, update the leaf, then recompute each ancestor on the way back.

Sum query on [1, 4] for arr = [2, 1, 5, 3, 4, 2]

Root [0, 5] = 17; children [0, 2] = 8 and [3, 5] = 9

sum(1..4) = 1 + 5 + 7 = 13. Only O(log n) nodes contribute; the node [3, 4] answered two elements at once without visiting its leaves.

Implementation

1class SegmentTree {2  constructor(arr) {3    this.n = arr.length;4    this.tree = new Array(4 * this.n).fill(0);5    this.#build(arr, 1, 0, this.n - 1);6  }7 8  #build(arr, node, start, end) {9    if (start === end) {10      this.tree[node] = arr[start];11      return;12    }13    const mid = (start + end) >> 1;14    this.#build(arr, 2 * node, start, mid);15    this.#build(arr, 2 * node + 1, mid + 1, end);16    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];17  }18 19  update(index, value, node = 1, start = 0, end = this.n - 1) {20    if (start === end) {21      this.tree[node] = value;22      return;23    }24    const mid = (start + end) >> 1;25    if (index <= mid) this.update(index, value, 2 * node, start, mid);26    else this.update(index, value, 2 * node + 1, mid + 1, end);27    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];28  }29 30  query(l, r, node = 1, start = 0, end = this.n - 1) {31    if (r < start || end < l) return 0;              // no overlap32    if (l <= start && end <= r) return this.tree[node]; // full overlap33    const mid = (start + end) >> 1;34    return this.query(l, r, 2 * node, start, mid) + this.query(l, r, 2 * node + 1, mid + 1, end);35  }36}37 38const st = new SegmentTree([2, 1, 5, 3, 4, 2]);39st.query(1, 4); // 1340st.update(2, 10);41st.query(1, 4); // 18

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Allocating 2n instead of 4n for the recursive version.

  Fix: Use 4n to avoid index overflow for non-power-of-two sizes.

• Wrong identity for min queries.

  Fix: Return Infinity for no overlap, not 0.

• Forgetting to push lazy values before recursing.

  Fix: Push pending updates to children before visiting them in partial overlaps.

Interview questions

Practice problems