Aba Nicaisse

The last two articles in this series dealt with flat, mostly static data. Binary search requires your array to be sorted and unchanged. Quickselect mutates the array and works best as a one-shot operation. Both fall apart the moment your data is dynamic, elements changing, queries arriving continuously, and correctness required after every mutation. This is the problem segment trees solve. And they solve it elegantly: O(log n) per query, O(log n) per update, and the same structure handles a surprisingly wide family of problems: range sums, range minimums, range maximums, and beyond.

1. The problem a flat array can't solve efficiently

Imagine you have an array of integers and two operations that interleave arbitrarily:

Query: what is the sum of elements from index l to index r?
Update: set arr[i] to a new value

With a plain array, a query scans from l to r — O(n) per query. With a prefix sum array, queries are O(1) but updates require rebuilding O(n) per update. Neither is acceptable when both operations are frequent.

Approach	Query	Update
Plain array	O(n)	O(1)
Prefix sum array	O(1)	O(n)
Segment tree	O(log n)	O(log n)

Segment trees sit exactly in the middle, neither operation dominates the other. That balance is precisely why they're the standard tool for this class of problem.

2. The structure: a tree of intervals

A segment tree is a binary tree where:

Each leaf node represents a single element of the array
Each internal node represents an interval — storing the aggregate (sum, min, max) of all elements in that interval
The root represents the entire array

For an array of size n, the tree has at most 4n nodes — a standard safe allocation. Here's what the structure looks like for [3, 1, 4, 1, 5, 9, 2, 6]:

Every node at interval [l..r] stores the sum of arr[l] through arr[r]. The root stores the sum of the entire array.

3. Building the tree

Building follows a simple post-order traversal: build left subtree, build right subtree, combine. The tree is stored in a flat array using the same indexing trick as a binary heap — node at index i has children at 2i and 2i + 1.

typescript

class SegmentTree {
  private readonly tree: number[];
  private readonly n: number;

  constructor(private readonly data: number[]) {
    this.n = data.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(1, 0, this.n - 1);
  }

  private build(node: number, lo: number, hi: number): void {
    if (lo === hi) {
      this.tree[node] = this.data[lo];
      return;
    }

    const mid = lo + Math.floor((hi - lo) / 2);
    this.build(2 * node, lo, mid);
    this.build(2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
}

Build time is O(n); each of the n leaves is visited once, and internal nodes are computed bottom-up in a single pass. The 4n allocation guarantees no out-of-bounds access regardless of whether n is a power of two.

4. Point update - O(log n)

When a single element changes, you update the leaf and propagate the change upward through every ancestor. Since tree height is O(log n), only O(log n) nodes are touched.

typescript

  // Updates arr[idx] to newValue and propagates change up the tree
  update(idx: number, newValue: number): void {
    this.updateHelper(1, 0, this.n - 1, idx, newValue);
  }

  private updateHelper(
    node: number,
    lo: number,
    hi: number,
    idx: number,
    newValue: number
  ): void {
    if (lo === hi) {
      this.tree[node] = newValue;
      return;
    }

    const mid = lo + Math.floor((hi - lo) / 2);

    if (idx <= mid) {
      this.updateHelper(2 * node, lo, mid, idx, newValue);
    } else {
      this.updateHelper(2 * node + 1, mid + 1, hi, idx, newValue);
    }

    // Recompute this node from its (now updated) children
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

Notice the pattern: navigate down to the leaf, then recompute every ancestor on the way back up. No other nodes are touched. If n = 1,000,000, at most 20 nodes are updated per call.

5. Range query - O(log n)

The query is the most elegant part of the segment tree. When you ask for the sum over [l..r], the tree can answer using pre-aggregated intervals — you never scan individual elements.

Three cases arise at each node during traversal:

The node's interval is completely outside [l..r] → return 0 (neutral element for sum)
The node's interval is completely inside [l..r] → return the stored aggregate directly
The node's interval partially overlaps [l..r] → recurse into both children

typescript

// Returns sum of arr[l..r] inclusive
  query(l: number, r: number): number {
    if (l < 0 || r >= this.n || l > r) {
      throw new RangeError(`Invalid query range [${l}, ${r}] for array of size ${this.n}`);
    }
    return this.queryHelper(1, 0, this.n - 1, l, r);
  }

  private queryHelper(
    node: number,
    lo: number,
    hi: number,
    l: number,
    r: number
  ): number {
    if (r < lo || hi < l) return 0;         // completely outside
    if (l <= lo && hi <= r) return this.tree[node]; // completely inside

    const mid = lo + Math.floor((hi - lo) / 2);
    const leftSum = this.queryHelper(2 * node, lo, mid, l, r);
    const rightSum = this.queryHelper(2 * node + 1, mid + 1, hi, l, r);
    return leftSum + rightSum;
  }

In the worst case, the query visits O(4 log n) nodes — a well-known bound for segment tree queries. In practice it's usually far fewer, because many intervals fall cleanly inside or outside the query range.

6. Making it generic: sum, min, max, or anything associative

The sum-specific logic lives in exactly two places: the + operator in build/update, and the 0 neutral element in query. Extracting those makes the entire structure reusable for any associative operation.

typescript

interface SegmentTreeConfig<T> {
  identity: T;                          // neutral element: 0 for sum, Infinity for min
  combine: (a: T, b: T) => T;          // associative operation
}

class GenericSegmentTree<T> {
  private readonly tree: T[];
  private readonly n: number;
  private readonly identity: T;
  private readonly combine: (a: T, b: T) => T;

  constructor(data: T[], config: SegmentTreeConfig<T>) {
    this.n = data.length;
    this.identity = config.identity;
    this.combine = config.combine;
    this.tree = new Array(4 * this.n).fill(this.identity);
    this.build(1, 0, this.n - 1, data);
  }

  private build(node: number, lo: number, hi: number, data: T[]): void {
    if (lo === hi) {
      this.tree[node] = data[lo];
      return;
    }
    const mid = lo + Math.floor((hi - lo) / 2);
    this.build(2 * node, lo, mid, data);
    this.build(2 * node + 1, mid + 1, hi, data);
    this.tree[node] = this.combine(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  update(idx: number, value: T): void {
    this.updateHelper(1, 0, this.n - 1, idx, value);
  }

  private updateHelper(node: number, lo: number, hi: number, idx: number, value: T): void {
    if (lo === hi) { this.tree[node] = value; return; }
    const mid = lo + Math.floor((hi - lo) / 2);
    if (idx <= mid) this.updateHelper(2 * node, lo, mid, idx, value);
    else this.updateHelper(2 * node + 1, mid + 1, hi, idx, value);
    this.tree[node] = this.combine(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  query(l: number, r: number): T {
    return this.queryHelper(1, 0, this.n - 1, l, r);
  }

  private queryHelper(node: number, lo: number, hi: number, l: number, r: number): T {
    if (r < lo || hi < l) return this.identity;
    if (l <= lo && hi <= r) return this.tree[node];
    const mid = lo + Math.floor((hi - lo) / 2);
    return this.combine(
      this.queryHelper(2 * node, lo, mid, l, r),
      this.queryHelper(2 * node + 1, mid + 1, hi, l, r)
    );
  }
}

// Range sum tree
const sumTree = new GenericSegmentTree<number>(
  [3, 1, 4, 1, 5, 9, 2, 6],
  { identity: 0, combine: (a, b) => a + b }
);

// Range minimum tree
const minTree = new GenericSegmentTree<number>(
  [3, 1, 4, 1, 5, 9, 2, 6],
  { identity: Infinity, combine: Math.min }
);

// Range maximum tree
const maxTree = new GenericSegmentTree<number>(
  [3, 1, 4, 1, 5, 9, 2, 6],
  { identity: -Infinity, combine: Math.max }
);

console.log(sumTree.query(1, 5)); // 20  (1+4+1+5+9)
console.log(minTree.query(1, 5)); // 1
console.log(maxTree.query(1, 5)); // 9

The combine function must be associative — the order of grouping can't change the result. Addition, min, max, GCD, bitwise OR/AND all qualify. Subtraction and division don't.

7. Range updates need lazy propagation

Point updates are clean. But what if you need to add 5 to every element from index l to r? Naively calling update for each index is O(n log n). The correct answer is lazy propagation, defer the update, mark the node as "pending", and push the deferred value down only when a child is actually accessed.

Lazy propagation is a significant extension that deserves its own article. The key thing to know now: without it, range updates degrade your segment tree to O(n log n) per operation, erasing its entire advantage.

typescript

// ❌ Naive range update — O(n log n), defeats the purpose
for (let i = l; i <= r; i++) {
  tree.update(i, tree.query(i, i) + delta);
}

// ✅ Lazy propagation handles this in O(log n)
// — covered in the next article in this series
tree.rangeUpdate(l, r, delta); // O(log n) with lazy propagation

TL;DR

Segment trees solve the dynamic range query problem: O(log n) per query and O(log n) per update, where plain arrays force a tradeoff between the two.
The tree stores pre-aggregated intervals. Queries combine at most O(4 log n) pre-computed nodes rather than scanning individual elements.
Updates touch only the target leaf and its O(log n) ancestors.
Any associative operation: sum, min, max, GCD, works with the same structure. Swap out combine and identity.
Range updates (adding a value to an entire interval) require lazy propagation. Without it, range updates are O(n log n). That's next.

Segment trees: answer any range query in O(log n) and update just as fast

In this article

1. The problem a flat array can't solve efficiently

2. The structure: a tree of intervals

3. Building the tree

4. Point update - O(log n)

5. Range query - O(log n)

6. Making it generic: sum, min, max, or anything associative

7. Range updates need lazy propagation

TL;DR

Get articles like this in your inbox