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.
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