Segment Tree

A segment tree is a binary tree built over an array where each node stores the answer to a query (sum, min, max, GCD…) for a contiguous subarray. It solves the classic range query + point update problem in O(log n) per operation — far better than the O(n) brute-force scan or the O(n) update cost of a prefix-sum array.

Note

Segment trees appear constantly in competitive programming and in backend systems that need fast rolling aggregates over time-series data.

The Range Query Problem

Given an array A of n elements, efficiently answer:

Range Sum Query (RSQ): What is the sum of A[l..r]?
Range Min/Max Query (RMQ): What is the minimum in A[l..r]?
Point Update: Set A[i] = v and keep all future queries correct.

Approach	Build	Query	Update	Space
Brute force	O(1)	O(n)	O(1)	O(1) extra
Prefix sum array	O(n)	O(1)	O(n)	O(n)
Segment tree	O(n)	O(log n)	O(log n)	O(n)
Fenwick (BIT)	O(n)	O(log n)	O(log n)	O(n)

Tree Structure (Array Representation)

Store the segment tree in a flat array tree[] of size 4n. For a node at index i:

Left child → 2i
Right child → 2i + 1
Parent → Math.floor(i / 2)

This avoids pointer overhead and is cache-friendly.

Text

Array A: [1, 3, 5, 7, 9, 11]   (indices 0-5)

                 tree[1] = 36       (sum of A[0..5])
                /                \
       tree[2] = 9              tree[3] = 27
       (A[0..2])                (A[3..5])
       /       \               /        \
  tree[4]=4  tree[5]=5  tree[6]=16  tree[7]=11
  (A[0..1])  (A[2..2])  (A[3..4])   (A[5..5])
  /      \              /      \
t[8]=1  t[9]=3      t[12]=7  t[13]=9
(A[0])  (A[1])      (A[3])   (A[4])

Build — O(n)

Recursively build from the leaves up. Each internal node merges its two children. Total work is O(n) because there are 2n − 1 nodes and each is visited once.

class SegmentTree {
  constructor(arr, merge = (a, b) => a + b, identity = 0) {
    this.n       = arr.length;
    this.merge   = merge;       // swap to Math.min / Math.max for RMQ
    this.identity = identity;   // 0 for sum, Infinity for min
    this.tree    = new Array(4 * this.n).fill(identity);
    this._build(arr, 1, 0, this.n - 1);
  }

  _build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
      return;
    }
    const mid = (start + end) >> 1;
    this._build(arr, 2 * node,     start, mid);
    this._build(arr, 2 * node + 1, mid + 1, end);
    this.tree[node] = this.merge(this.tree[2 * node], this.tree[2 * node + 1]);
  }
}

Range Query — O(log n)

Three cases at each node during the query:

No overlap — the node's range is entirely outside [l, r]: return identity.
Full overlap — the node's range is entirely inside [l, r]: return node value.
Partial overlap — recurse into both children and merge.

  // Range query on A[l..r]  (0-indexed, inclusive)
  query(l, r) {
    return this._query(1, 0, this.n - 1, l, r);
  }

  _query(node, start, end, l, r) {
    if (r < start || end < l) return this.identity;   // no overlap
    if (l <= start && end <= r) return this.tree[node]; // full overlap
    const mid = (start + end) >> 1;
    const left  = this._query(2 * node,     start, mid,   l, r);
    const right = this._query(2 * node + 1, mid+1, end,   l, r);
    return this.merge(left, right);
  }

Point Update — O(log n)

Update A[idx] = val. Walk from the root to the target leaf, updating every ancestor on the way back up.

  // Point update: set A[idx] = val
  update(idx, val) {
    this._update(1, 0, this.n - 1, idx, val);
  }

  _update(node, start, end, idx, val) {
    if (start === end) {
      this.tree[node] = val;
      return;
    }
    const mid = (start + end) >> 1;
    if (idx <= mid) this._update(2 * node,     start, mid,   idx, val);
    else            this._update(2 * node + 1, mid+1, end,   idx, val);
    this.tree[node] = this.merge(this.tree[2 * node], this.tree[2 * node + 1]);
  }
}

Full Range Sum Demo

const A = [1, 3, 5, 7, 9, 11];
const st = new SegmentTree(A);   // default: sum, identity=0

console.log(st.query(1, 4));     // 3+5+7+9 = 24
console.log(st.query(0, 5));     // 36  (whole array)

st.update(1, 10);                // A[1] = 10  (was 3)
console.log(st.query(1, 4));     // 10+5+7+9 = 31

24
36
31

Range Minimum Query (RMQ)

Pass Math.min as the merge function and Infinity as the identity. Everything else is identical.

const rmq = new SegmentTree([2, 4, 3, 1, 6, 7, 8, 5], Math.min, Infinity);

console.log(rmq.query(0, 7));  // 1  (whole array min)
console.log(rmq.query(2, 5));  // 1  (min of A[2..5] = 3,1,6,7)
console.log(rmq.query(4, 7));  // 5  (min of A[4..7] = 6,7,8,5)

1
1
5

Lazy Propagation — Range Updates in O(log n)

A naive "add v to every element in A[l..r]" would take O(n·log n) point updates. Lazy propagation defers the work: store a pending update on each node and push it down only when you need to descend further.

Text

Idea: attach a "lazy tag" to each node.

When we range-update node covering [s..e] by +v:
  1. Update tree[node] immediately  (tree[node] += v * (e - s + 1) for sum)
  2. Store lazy[node] += v          (defer children update)

When we later need to visit children:
  _pushDown: propagate lazy[node] to children, then clear it.

class LazySegTree {
  constructor(arr) {
    this.n    = arr.length;
    this.tree = new Array(4 * arr.length).fill(0);
    this.lazy = new Array(4 * arr.length).fill(0);
    this._build(arr, 1, 0, arr.length - 1);
  }

  _build(arr, node, s, e) {
    if (s === e) { this.tree[node] = arr[s]; return; }
    const m = (s + e) >> 1;
    this._build(arr, 2*node,   s,   m);
    this._build(arr, 2*node+1, m+1, e);
    this.tree[node] = this.tree[2*node] + this.tree[2*node+1];
  }

  _pushDown(node, s, e) {
    if (this.lazy[node] === 0) return;
    const m   = (s + e) >> 1;
    const lc  = 2 * node, rc = 2 * node + 1;
    const add = this.lazy[node];

    this.tree[lc]  += add * (m - s + 1);
    this.lazy[lc]  += add;
    this.tree[rc]  += add * (e - m);
    this.lazy[rc]  += add;
    this.lazy[node] = 0;
  }

  // Range add: A[l..r] += val
  rangeAdd(l, r, val) {
    this._rangeAdd(1, 0, this.n - 1, l, r, val);
  }

  _rangeAdd(node, s, e, l, r, val) {
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
      this.tree[node] += val * (e - s + 1);
      this.lazy[node] += val;
      return;
    }
    this._pushDown(node, s, e);
    const m = (s + e) >> 1;
    this._rangeAdd(2*node,   s,   m, l, r, val);
    this._rangeAdd(2*node+1, m+1, e, l, r, val);
    this.tree[node] = this.tree[2*node] + this.tree[2*node+1];
  }

  // Range sum query A[l..r]
  query(l, r) {
    return this._query(1, 0, this.n - 1, l, r);
  }

  _query(node, s, e, l, r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return this.tree[node];
    this._pushDown(node, s, e);
    const m = (s + e) >> 1;
    return this._query(2*node, s, m, l, r)
         + this._query(2*node+1, m+1, e, l, r);
  }
}

// ── Demo ──────────────────────────────────────────────
const lst = new LazySegTree([1, 2, 3, 4, 5]);

console.log(lst.query(0, 4));   // 15
lst.rangeAdd(1, 3, 10);         // A[1..3] += 10  → [1, 12, 13, 14, 5]
console.log(lst.query(0, 4));   // 45
console.log(lst.query(1, 3));   // 39

15
45
39

Tip

For range-assign (set every element in a range to a value) instead of range-add, track a separate "assign flag" per node and handle the precedence between assign and add in pushDown carefully.

Classic Interview Problem — Count of Smaller Numbers After Self

Given array nums, return counts[i] = number of elements to the right of nums[i] that are smaller. One approach: coordinate-compress values to [0..n-1], then scan right-to-left with a Fenwick/segment tree that supports point-add and prefix-sum query.

function countSmaller(nums) {
  // Coordinate compression
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const rank   = new Map(sorted.map((v, i) => [v, i + 1]));  // 1-indexed
  const m      = sorted.length;

  // BIT (Fenwick tree) for fast point-add + prefix-sum
  const bit = new Array(m + 1).fill(0);
  const add  = (i, v) => { for (; i <= m; i += i & -i) bit[i] += v; };
  const sum  = (i)    => { let s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; };

  const result = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    const r = rank.get(nums[i]);
    result.unshift(sum(r - 1));   // count of elements < nums[i] already inserted
    add(r, 1);
  }
  return result;
}

console.log(countSmaller([5, 2, 6, 1]));  // [2, 1, 1, 0]

[2, 1, 1, 0]

Range Max with Point Update

// Reuse the generic SegmentTree with Math.max / -Infinity
const maxST = new SegmentTree([3, 1, 4, 1, 5, 9, 2, 6], Math.max, -Infinity);

console.log(maxST.query(0, 7));  // 9
console.log(maxST.query(0, 4));  // 5
maxST.update(5, 0);              // knock 9 down to 0
console.log(maxST.query(0, 7));  // 6

9
5
6

Applications

Problem	Merge fn	Identity	Extra notes
Range sum	a + b	0	Classic use case
Range min / max	Math.min / max	±Infinity	RMQ; used in LCA algorithms
Range GCD	gcd(a, b)	0	gcd(0, x) = x is the identity
Count elements in range	a + b	0	Coordinate-compress first
Range XOR	a ^ b	0	XOR is its own inverse
Lazy range add + sum	a + b with lazy	0	O(log n) bulk updates
Interval scheduling	max overlap merge	—	Node stores (max_prefix, sum, max_suffix)

Iterative (Bottom-Up) Segment Tree

For sum queries without lazy propagation, an iterative implementation is simpler and faster in practice. Leaves occupy tree[n..2n-1]; internal nodes tree[1..n-1].

class IterSegTree {
  constructor(arr) {
    this.n = arr.length;
    this.t = new Array(2 * arr.length).fill(0);
    // fill leaves
    for (let i = 0; i < arr.length; i++) this.t[i + arr.length] = arr[i];
    // build internal nodes
    for (let i = arr.length - 1; i > 0; i--) this.t[i] = this.t[2*i] + this.t[2*i+1];
  }

  // Point update A[pos] = val
  update(pos, val) {
    pos += this.n;
    this.t[pos] = val;
    for (pos >>= 1; pos >= 1; pos >>= 1) {
      this.t[pos] = this.t[2*pos] + this.t[2*pos+1];
    }
  }

  // Range sum A[l..r]  (inclusive)
  query(l, r) {
    let res = 0;
    for (l += this.n, r += this.n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += this.t[l++];
      if (r & 1) res += this.t[--r];
    }
    return res;
  }
}

const ist = new IterSegTree([1, 3, 5, 7, 9, 11]);
console.log(ist.query(1, 4));   // 24
ist.update(1, 10);
console.log(ist.query(1, 4));   // 31

24
31

Warning

The iterative tree requires the array size to be exactly n (no padding needed), but the internal-node indexing assumes 1-indexed nodes. Be careful when mixing 0-indexed positions with the node arithmetic — always add this.n when converting from array index to tree index.

Complexity Summary

Operation	Recursive	Iterative	Lazy (range update)
Build	O(n)	O(n)	O(n)
Point update	O(log n)	O(log n)	O(log n)
Range query	O(log n)	O(log n)	O(log n)
Range update	O(n log n) naive	—	O(log n) with lazy
Space	O(4n)	O(2n)	O(4n) + O(4n) lazy

Interview Cheat Sheet

Scenario	Use
Static array, many range queries, no updates	Prefix sum (simpler, O(1) query)
Dynamic array, point updates + range queries	Segment tree or Fenwick tree
Range updates (add/assign) + range queries	Lazy segment tree
Range min/max with point updates	Segment tree with Math.min/max
Count inversions / smaller-to-right	Fenwick tree + coordinate compression
2D range queries	Merge-sort tree or 2D segment tree

Key Takeaways

A segment tree answers range queries and point updates in O(log n) by storing pre-computed results for every interval at every level.
Store the tree in a flat array (1-indexed); children of node i are 2i and 2i+1.
The merge function (sum, min, max, GCD, XOR …) is the only thing that changes between variants.
Use identity = 0 for sum/XOR, ±Infinity for min/max so out-of-range nodes never corrupt results.
Lazy propagation defers bulk range updates to O(log n) by tagging nodes and pushing down only when needed.
The iterative (bottom-up) variant uses half the space (2n) and avoids recursion overhead for sum/max without lazy needs.
Always coordinate-compress when the value range is large but the number of distinct values is small.