Advanced Trees

Segment Tree

What is a Segment Tree?

A Segment Tree answers a question that neither a plain array nor a running-total (prefix-sum) array handles well at the same time: "what's the sum (or min, max, gcd...) of elements from index l to r?", while also supporting fast updates to individual elements. A prefix-sum array answers range queries in O(1), but a single update forces you to recompute every prefix after it — O(n) per update. A segment tree gets both operations down to O(log n).

How Is It Built?

Every node in a segment tree represents a contiguous range of the underlying array. Leaves represent single elements; every internal node represents the union of its two children's ranges, and stores the combined result of some associative operation (sum, min, max, etc.) over that whole range — computed once and cached, not recomputed from scratch on every query.

Sum segment tree built over [2, 5, 1, 4]
12[0,3]7[0,1]5[2,3]2[0,0]5[1,1]1[2,2]4[3,3]
Leaf (single element)Internal (cached range sum)

How Does a Range Query Work?

A range query works by decomposing the query range into a small number of these pre-combined node ranges. Starting from the root, if a node's range falls entirely outside the query, it's skipped. If it falls entirely inside the query, its cached value is used directly — no need to look at its children at all. Only when a node's range partially overlaps the query does the search recurse into both children. This decomposition never needs more than O(log n) nodes to cover any range.

How Does a Point Update Work?

A point update walks straight from the root down to the one leaf that needs to change, updates it, and then recomputes each ancestor's cached value on the way back up — exactly one path of length O(log n), touching nothing else in the tree.

Algorithm Steps

  1. Build: recursively split [l, r] at its midpoint until reaching single-element leaves, then combine each pair of children's results going back up
  2. Range Query(ql, qr) on the current node's range [l, r]:
    • If [l, r] is entirely outside [ql, qr], return the operation's identity (0 for sum) and stop
    • If [l, r] is entirely inside [ql, qr], return this node's cached value directly
    • Otherwise, recurse into both children and combine their results
  3. Point Update(index, value): descend to the leaf for that index, set its value, then recompute every ancestor's cached value on the way back up

Time Complexity

  • Build: O(n) — every node is computed exactly once.
  • Range Query: O(log n) — at most a constant number of nodes per level are visited.
  • Point Update: O(log n) — exactly one root-to-leaf path is touched.

Time Complexity Analysis

Advertisement
Daily DSA Challenge by Scale Engineer

Build a segment tree over an array, then update a value or query a range

No segment tree yet — build one over a random array
No tree yet — build one over a random array
Leaf (array element)Internal (range sum)Update pathQuery: fully inside rangeQuery: partially overlapsQuery: outside range

Test Your Knowledge before moving forward!

Segment Tree Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Segment Tree Implementation

// Sum Segment Tree, built over an array using a flat 1-indexed array
// representation (node i's children are at 2i and 2i+1)
class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }

  build(arr, node, l, r) {
    if (l === r) {
      this.tree[node] = arr[l];
      return;
    }
    const mid = Math.floor((l + r) / 2);
    this.build(arr, 2 * node, l, mid);
    this.build(arr, 2 * node + 1, mid + 1, r);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

  // Point update: set arr[index] = value
  update(index, value, node = 1, l = 0, r = this.n - 1) {
    if (l === r) {
      this.tree[node] = value;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (index <= mid) this.update(index, value, 2 * node, l, mid);
    else this.update(index, value, 2 * node + 1, mid + 1, r);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

  // Range sum query over [ql, qr]
  query(ql, qr, node = 1, l = 0, r = this.n - 1) {
    if (qr < l || r < ql) return 0;              // fully outside — identity element
    if (ql <= l && r <= qr) return this.tree[node]; // fully inside — use cached value
    const mid = Math.floor((l + r) / 2);
    return (
      this.query(ql, qr, 2 * node, l, mid) +
      this.query(ql, qr, 2 * node + 1, mid + 1, r)
    );
  }
}

// Usage example
const st = new SegmentTree([2, 5, 1, 4, 9, 3]);
st.query(1, 3);   // 5 + 1 + 4 = 10
st.update(2, 10); // arr becomes [2, 5, 10, 4, 9, 3]
st.query(1, 3);   // 5 + 10 + 4 = 19

Done With the Learning

Mark Segment Tree as done and view it on your dashboard

Explore Other Tree Topics

Fenwick Tree

B-Tree

Trie (Prefix Tree)

Red-Black Tree

AVL Balancing

BST Insertion