All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Segment Trees — Range Queries & Updates

Segment Trees — Range Queries & Updates

0/12 in this phase0/57 across the roadmap

📖 Concept

A segment tree is a binary tree that stores information about array segments, enabling O(log n) range queries AND updates. Unlike prefix sum (O(1) query, O(n) update), segment trees balance both.

Use when you need BOTH:

  • Range queries (sum, min, max over [l, r])
  • Point or range updates

Structure:

  • Leaf nodes: individual array elements
  • Internal nodes: aggregate (sum/min/max) of their children's range
  • Total nodes: ~4n (use array of size 4n)

Operations:

Operation Prefix Sum Segment Tree
Range query O(1) O(log n)
Point update O(n) O(log n)
Range update O(n) O(log n) with lazy propagation
Build O(n) O(n)

Lazy Propagation: For range updates, instead of updating all affected nodes immediately, "lazily" store the pending update and apply it only when that range is queried.

🏠 Real-world analogy: A company hierarchy. The CEO (root) knows total revenue. VPs know their division's revenue. Managers know their team's revenue. To find revenue for floors 3-7, you don't ask every employee — you ask the right managers and aggregate.

💻 Code Example

codeTap to expand ⛶
1// SEGMENT TREE — Sum range queries + point updates
2class SegmentTree {
3  constructor(arr) {
4    this.n = arr.length;
5    this.tree = new Array(4 * this.n).fill(0);
6    this.build(arr, 1, 0, this.n - 1);
7  }
8

9  build(arr, node, start, end) {
10    if (start === end) {
11      this.tree[node] = arr[start];
12      return;
13    }
14    const mid = Math.floor((start + end) / 2);
15    this.build(arr, 2 * node, start, mid);
16    this.build(arr, 2 * node + 1, mid + 1, end);
17    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
18  }
19

20  // Point update: set arr[idx] = val
21  update(idx, val, node = 1, start = 0, end = this.n - 1) {
22    if (start === end) {
23      this.tree[node] = val;
24      return;
25    }
26    const mid = Math.floor((start + end) / 2);
27    if (idx <= mid) this.update(idx, val, 2 * node, start, mid);
28    else this.update(idx, val, 2 * node + 1, mid + 1, end);
29    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
30  }
31

32  // Range query: sum of arr[l..r]
33  query(l, r, node = 1, start = 0, end = this.n - 1) {
34    if (r < start || end < l) return 0;  // Out of range
35    if (l <= start && end <= r) return this.tree[node]; // Fully in range
36    const mid = Math.floor((start + end) / 2);
37    return this.query(l, r, 2 * node, start, mid) +
38           this.query(l, r, 2 * node + 1, mid + 1, end);
39  }
40}
41

42// USAGE
43const arr = [1, 3, 5, 7, 9, 11];
44const st = new SegmentTree(arr);
45console.log(st.query(1, 3)); // 15 (3 + 5 + 7)
46st.update(2, 10);            // arr[2] = 10
47console.log(st.query(1, 3)); // 20 (3 + 10 + 7)
48

49// MIN SEGMENT TREE
50class MinSegTree {
51  constructor(arr) {
52    this.n = arr.length;
53    this.tree = new Array(4 * this.n).fill(Infinity);
54    this.build(arr, 1, 0, this.n - 1);
55  }
56  build(arr, node, s, e) {
57    if (s === e) { this.tree[node] = arr[s]; return; }
58    const mid = (s + e) >> 1;
59    this.build(arr, 2*node, s, mid);
60    this.build(arr, 2*node+1, mid+1, e);
61    this.tree[node] = Math.min(this.tree[2*node], this.tree[2*node+1]);
62  }
63  query(l, r, node = 1, s = 0, e = this.n - 1) {
64    if (r < s || e < l) return Infinity;
65    if (l <= s && e <= r) return this.tree[node];
66    const mid = (s + e) >> 1;
67    return Math.min(this.query(l,r,2*node,s,mid), this.query(l,r,2*node+1,mid+1,e));
68  }
69}

🏋️ Practice Exercise

Practice Problems:

  1. Implement a segment tree for range sum queries
  2. Implement point updates with the segment tree
  3. Implement a min/max segment tree
  4. Range sum query with both range update and range query (lazy propagation)
  5. Count inversions using a segment tree
  6. Find the minimum in a range and update a value
  7. Range XOR queries using segment tree
  8. Count of elements less than k in a range
  9. Merge sort tree (segment tree with sorted lists at each node)
  10. Persistent segment tree (conceptual)

⚠️ Common Mistakes

  • Using segment tree when prefix sum suffices — if no updates are needed, prefix sum is simpler and faster

  • Incorrect tree size — always allocate 4n, not 2n (the tree can be deeper than expected)

  • Off-by-one in range endpoints — be consistent with inclusive [l, r] boundaries

  • Not implementing lazy propagation for range updates — without it, range updates are O(n)

  • Confusing 0-indexed array with 1-indexed tree — the tree typically starts at index 1

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Segment Trees — Range Queries & Updates

← PreviousTries (Prefix Trees)Next →Binary Indexed Tree (Fenwick Tree)