Segment Trees Intro - Learning Module

Loading content...

0/276

Query Types: Sum, Min, Max, GCD

One Structure, Many Operations

The segment tree structure we built works for any associative operation. This is its true power—learn the pattern once, apply it to countless problems.

In this page, we'll implement segment trees for four common operations:

Sum: Total of elements in range
Minimum: Smallest element in range
Maximum: Largest element in range
GCD: Greatest common divisor of elements in range

For each, only two things change: the combine function and the identity element. The tree structure, query algorithm, and update algorithm remain identical.

What You Will Learn

By the end of this page, you'll be able to implement segment trees for any associative operation. You'll understand identity elements, see complete implementations for four major operations, and learn to create generic, reusable segment tree templates.

The Generic Segment Tree Pattern

Every segment tree operation follows this pattern:

Parameters to customize:

Combine function: (a, b) => result — How to merge two values
Identity element: A value e such that combine(e, x) = x for all x

The identity element handles edge cases:

Empty ranges
Nodes outside query range
Padding for non-power-of-2 sizes

Operation	Combine	Identity	Why Identity Works
Sum	a + b	0	0 + x = x
Min	min(a, b)	+∞	min(∞, x) = x
Max	max(a, b)	-∞	max(-∞, x) = x
GCD	gcd(a, b)	0	gcd(0, x) = x
Product	a × b	1	1 × x = x
XOR	a ⊕ b	0	0 ⊕ x = x
AND	a & b	all 1s	~0 & x = x
OR	a \| b	0	0 \| x = x

generic_segment_tree.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Generic Segment Tree - Works for ANY associative operation
 */
class GenericSegmentTree<T> {
  private tree: T[];
  private n: number;
  private combine: (a: T, b: T) => T;
  private identity: T;
 
  constructor(
    arr: T[],
    combine: (a: T, b: T) => T,
    identity: T
  ) {
    this.n = arr.length;
    this.combine = combine;
    this.identity = identity;
    this.tree = new Array(4 * this.n).fill(identity);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: T[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      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, start: number, end: number, L: number, R: number): T {
    if (R < start || L > end) return this.identity;
    if (L <= start && end <= R) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    return this.combine(
      this.queryHelper(2 * node, start, mid, L, R),
      this.queryHelper(2 * node + 1, mid + 1, end, L, R)
    );
  }
 
  update(index: number, value: T): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  private updateHelper(node: number, start: number, end: number, index: number, value: T): void {
    if (start === end) {
      this.tree[node] = value;
    } else {
      const mid = Math.floor((start + end) / 2);
      if (index <= mid) this.updateHelper(2 * node, start, mid, index, value);
      else this.updateHelper(2 * node + 1, mid + 1, end, index, value);
      this.tree[node] = this.combine(this.tree[2 * node], this.tree[2 * node + 1]);
    }
  }
}
 
// Usage examples:
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
 
const sumTree = new GenericSegmentTree(arr, (a, b) => a + b, 0);
const minTree = new GenericSegmentTree(arr, (a, b) => Math.min(a, b), Infinity);
const maxTree = new GenericSegmentTree(arr, (a, b) => Math.max(a, b), -Infinity);

The Power of Generics

With this generic template, you never rewrite segment tree logic. Just provide combine and identity. This is software engineering best practice: abstract the invariant structure, parameterize the variant behavior.

Range Sum Segment Tree

Range sum is the most common segment tree application. We've used it throughout, but let's formalize:

Operation: Sum of all elements A[L] + A[L+1] + ... + A[R] Combine: (a, b) => a + b Identity: 0 (adding zero doesn't change sum)

Properties of Sum:

Associative: (a + b) + c = a + (b + c) ✓
Commutative: a + b = b + a ✓
Has identity: a + 0 = a ✓
Invertible: can subtract to "undo" ✓

The invertibility is why prefix sums work for static data—but segment trees handle dynamic data better.

range_sum_tree.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class RangeSumTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      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.tree[2 * node] + this.tree[2 * node + 1]; // SUM
    }
  }
 
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  private queryHelper(node: number, start: number, end: number, L: number, R: number): number {
    if (R < start || L > end) return 0; // IDENTITY for sum
    if (L <= start && end <= R) return this.tree[node];
    const mid = (start + end) >> 1;
    return this.queryHelper(2 * node, start, mid, L, R) +
           this.queryHelper(2 * node + 1, mid + 1, end, L, R);
  }
 
  update(index: number, value: number): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = (start + end) >> 1;
      if (idx <= mid) this.updateHelper(2 * node, start, mid, idx, val);
      else this.updateHelper(2 * node + 1, mid + 1, end, idx, val);
      this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
    }
  }
}
 
// Example:
const st = new RangeSumTree([1, 3, 5, 7, 9, 11]);
console.log(st.query(1, 4)); // 3+5+7+9 = 24
st.update(2, 10);            // Change 5 to 10
console.log(st.query(1, 4)); // 3+10+7+9 = 29

Range Minimum Query (RMQ)

Range Minimum Query finds the smallest element in a range. It's used in:

Finding stock price lows over time periods
Lowest Common Ancestor (LCA) algorithms
Computational geometry applications

Operation: min(A[L], A[L+1], ..., A[R]) Combine: (a, b) => Math.min(a, b) Identity: +Infinity (min with infinity gives the other value)

Key Property - Idempotence: min(a, a) = a. This means overlapping ranges don't cause problems. Sparse tables exploit this for O(1) static queries—but for dynamic data, segment trees are needed.

range_min_tree.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class RangeMinTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(Infinity);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = (start + end) >> 1;
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      this.tree[node] = Math.min(this.tree[2 * node], this.tree[2 * node + 1]); // MIN
    }
  }
 
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  private queryHelper(node: number, start: number, end: number, L: number, R: number): number {
    if (R < start || L > end) return Infinity; // IDENTITY for min
    if (L <= start && end <= R) return this.tree[node];
    const mid = (start + end) >> 1;
    return Math.min(
      this.queryHelper(2 * node, start, mid, L, R),
      this.queryHelper(2 * node + 1, mid + 1, end, L, R)
    );
  }
 
  update(index: number, value: number): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = (start + end) >> 1;
      if (idx <= mid) this.updateHelper(2 * node, start, mid, idx, val);
      else this.updateHelper(2 * node + 1, mid + 1, end, idx, val);
      this.tree[node] = Math.min(this.tree[2 * node], this.tree[2 * node + 1]);
    }
  }
}
 
// Example:
const rmq = new RangeMinTree([5, 2, 8, 1, 9, 3]);
console.log(rmq.query(0, 5)); // 1 (minimum of entire array)
console.log(rmq.query(2, 4)); // 1 (min of [8, 1, 9])
rmq.update(3, 10);            // Change 1 to 10
console.log(rmq.query(2, 4)); // 8 (min of [8, 10, 9])

Finding the Index of Minimum

Often you need the INDEX of the minimum, not just the value. Store pairs (value, index) in the tree. Combine by comparing values: keep the pair with smaller value. Query returns both the min value and its position.

Range Maximum Query

Range Maximum Query is the mirror of RMQ:

Operation: max(A[L], A[L+1], ..., A[R]) Combine: (a, b) => Math.max(a, b) Identity: -Infinity

Applications include:

Finding stock price highs
Maximum segment problems
Game leaderboard queries

range_max_tree.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class RangeMaxTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(-Infinity);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = (start + end) >> 1;
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]); // MAX
    }
  }
 
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  private queryHelper(node: number, start: number, end: number, L: number, R: number): number {
    if (R < start || L > end) return -Infinity; // IDENTITY for max
    if (L <= start && end <= R) return this.tree[node];
    const mid = (start + end) >> 1;
    return Math.max(
      this.queryHelper(2 * node, start, mid, L, R),
      this.queryHelper(2 * node + 1, mid + 1, end, L, R)
    );
  }
 
  update(index: number, value: number): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = (start + end) >> 1;
      if (idx <= mid) this.updateHelper(2 * node, start, mid, idx, val);
      else this.updateHelper(2 * node + 1, mid + 1, end, idx, val);
      this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]);
    }
  }
}
 
// Example:
const maxTree = new RangeMaxTree([5, 2, 8, 1, 9, 3]);
console.log(maxTree.query(0, 5)); // 9 (maximum of entire array)
console.log(maxTree.query(0, 2)); // 8 (max of [5, 2, 8])

Range GCD Query

Range GCD finds the greatest common divisor of all elements in a range. It's useful in number theory problems and cryptographic applications.

Operation: gcd(A[L], A[L+1], ..., A[R]) Combine: (a, b) => gcd(a, b) Identity: 0 (gcd(0, x) = x)

Why GCD Works:

Associative: gcd(gcd(a,b), c) = gcd(a, gcd(b,c)) ✓
Commutative: gcd(a, b) = gcd(b, a) ✓
Idempotent: gcd(a, a) = a ✓
Has identity: gcd(0, x) = x ✓

range_gcd_tree.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// Euclidean GCD algorithm
function gcd(a: number, b: number): number {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
 
class RangeGCDTree {
  private tree: number[];
  private n: number;
 
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
 
  private build(arr: number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = (start + end) >> 1;
      this.build(arr, 2 * node, start, mid);
      this.build(arr, 2 * node + 1, mid + 1, end);
      this.tree[node] = gcd(this.tree[2 * node], this.tree[2 * node + 1]); // GCD
    }
  }
 
  query(L: number, R: number): number {
    return this.queryHelper(1, 0, this.n - 1, L, R);
  }
 
  private queryHelper(node: number, start: number, end: number, L: number, R: number): number {
    if (R < start || L > end) return 0; // IDENTITY for GCD
    if (L <= start && end <= R) return this.tree[node];
    const mid = (start + end) >> 1;
    return gcd(
      this.queryHelper(2 * node, start, mid, L, R),
      this.queryHelper(2 * node + 1, mid + 1, end, L, R)
    );
  }
 
  update(index: number, value: number): void {
    this.updateHelper(1, 0, this.n - 1, index, value);
  }
 
  private updateHelper(node: number, start: number, end: number, idx: number, val: number): void {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = (start + end) >> 1;
      if (idx <= mid) this.updateHelper(2 * node, start, mid, idx, val);
      else this.updateHelper(2 * node + 1, mid + 1, end, idx, val);
      this.tree[node] = gcd(this.tree[2 * node], this.tree[2 * node + 1]);
    }
  }
}
 
// Example:
const gcdTree = new RangeGCDTree([12, 18, 24, 36, 48]);
console.log(gcdTree.query(0, 4)); // 6 (GCD of all)
console.log(gcdTree.query(1, 3)); // 6 (GCD of 18, 24, 36)
gcdTree.update(2, 15);            // Change 24 to 15
console.log(gcdTree.query(0, 4)); // 3 (GCD of 12, 18, 15, 36, 48)

Operation Comparison and Selection Guide

Complete Comparison of Segment Tree Operations
Operation	Combine	Identity	Idempotent	Common Use Cases
Sum	a + b	0	No	Totals, counts, averages
Min	min(a,b)	+∞	Yes	Lowest price, RMQ, LCA
Max	max(a,b)	-∞	Yes	Highest score, peak finding
GCD	gcd(a,b)	0	Yes	Number theory, coprimality
LCM	lcm(a,b)	1	Yes	Synchronization problems
AND	a & b	~0	Yes	Bit intersection queries
OR	a \| b	0	Yes	Bit union queries
XOR	a ^ b	0	No	Parity, toggle state
Product	a × b	1	No	Factorial ranges, probabilities

Choosing Your Operation

Most competitive programming problems use Sum, Min, or Max. GCD appears in number theory contexts. XOR is useful for parity and duplicate-finding problems. If your operation is associative and has an identity element, segment trees will work.

Module Summary: Mastering Segment Trees

Key Concepts from This Module

•Range queries are ubiquitous—from analytics to games to databases.
•Naive approaches fail when both queries and updates must be fast.
•Prefix sums break under updates—O(n) per change is unacceptable.
•Hierarchical decomposition is the key insight: store aggregates at multiple granularities.
•Segment trees achieve O(log n) for both queries and updates with O(n) space.
•The structure is universal: same algorithm works for any associative operation.
•Only combine and identity change between Sum, Min, Max, GCD, etc.

What's Next in Chapter 27:

This module covered the foundational segment tree structure. The chapter continues with:

Module 2: Building and implementing segment trees in detail
Module 3: Lazy propagation for efficient range updates
Module 4: Fenwick Trees (BIT) as a simpler alternative
And more advanced data structures...

You now have the conceptual foundation. Practice implementing these trees from scratch until the pattern becomes second nature.

Module Complete!

Congratulations! You've mastered the segment tree concept—from understanding why simpler approaches fail, through the divide-and-conquer structure, to implementing various query types. This knowledge is essential for any serious algorithm practitioner.