What are Segment Trees useful for?

They are used for range queries (Sum, Min, Max, GCD) and efficient updates on an underlying array in O(log n) time.

Segment Tree vs Fenwick Tree?

Segment Trees are more versatile as they can handle non-invertible operations (like Range Max). Fenwick Trees are more space-efficient and simpler to code for Range Sums.

What is the space complexity?

A Segment Tree typically requires O(4n) space where n is the number of elements in the base array.

Segment Tree

A segment tree is a tree data structure that stores intervals or segments, allowing efficient range queries and updates.

READY

The array underneath

Every node stores the sum of its range. Query a range to see how few of them the answer actually needs.

Array

Sum from

Set index

Intuition

If you have an array and need to find the sum of elements from index L to R frequently, a simple loop takes O(n). A Segment Tree precomputes partial sums in a tree structure, allowing both queries and updates in O(log n).

Concept

A Segment Tree is a full binary tree where each node represents an interval. The root represents the entire array [0, n-1]. Its children represent the left half [0, mid] and right half [mid+1, n-1]. Leaves represent individual elements [i, i].

How it Works

Build: Construct tree from array. tree[i] = tree[2*i] + tree[2*i+1] (for sum).
Query(L, R): Combine values from nodes that are fully within [L, R].
Update(i, val): Update leaf node for index i and recalculate values up to the root.
Range Update: (Advanced) Uses Lazy Propagation to defer updates for O(log n).

Step-by-Step Breakdown

Query Logic (Range Sum):

Start at root covering [0, n-1].
If node's range is completely inside [L, R], return node value.
If node's range is completely outside [L, R], return 0.
Otherwise, partial overlap: recurse left and right, then sum the results.

When to Use

Range queries (Sum, Min, Max, GCD) on an array.
When element updates are frequent (unlike Prefix Sum which is static).
Computational Geometry (finding intersecting rectangles).

When NOT to Use

When the array is static (use Prefix Sum Array for O(1) query).
When memory is extremely tight (approx 4n space).
When high-dimensional data is involved (KD-Tree might be better).

How to Identify

Keywords: "Range Sum Query", "Range Minimum Query", "Mutable Array", "Frequent Updates".

AI resume checker — match your resume to the job description

Trie (Prefix Tree)

Fenwick Tree

Complexity

Time (Best)

O(log n)

Time (Average)

O(log n)

Time (Worst)

O(log n)

Space

O(n)

Segment Tree Code

1class SegmentTree {
2    constructor(arr) {
3        this.n = arr.length;
4        this.tree = new Array(4 * this.n).fill(0);
5        this.build(arr, 1, 0, this.n - 1);
6    }
7
8    build(arr, node, start, end) {
9        if (start === end) {
10            this.tree[node] = arr[start];
11        } else {
12            let mid = Math.floor((start + end) / 2);
13            this.build(arr, 2 * node, start, mid);
14            this.build(arr, 2 * node + 1, mid + 1, end);
15            this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
16        }
17    }
18
19    update(idx, val) {
20        this.updateHelper(1, 0, this.n - 1, idx, val);
21    }
22
23    updateHelper(node, start, end, idx, val) {
24        if (start === end) {
25            this.tree[node] = val;
26        } else {
27            let mid = Math.floor((start + end) / 2);
28            if (start <= idx && idx <= mid) {
29                this.updateHelper(2 * node, start, mid, idx, val);
30            } else {
31                this.updateHelper(2 * node + 1, mid + 1, end, idx, val);
32            }
33            this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
34        }
35    }
36
37    query(l, r) {
38        return this.queryHelper(1, 0, this.n - 1, l, r);
39    }
40
41    queryHelper(node, start, end, l, r) {
42        if (r < start || end < l) return 0;
43        if (l <= start && end <= r) return this.tree[node];
44        let mid = Math.floor((start + end) / 2);
45        let p1 = this.queryHelper(2 * node, start, mid, l, r);
46        let p2 = this.queryHelper(2 * node + 1, mid + 1, end, l, r);
47        return p1 + p2;
48    }
49}

Related Lessons

Segment Tree

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Range Sum Query - Mutable

Count of Range Sum

The Skyline Problem

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

What are Segment Trees useful for?

Segment Tree vs Fenwick Tree?

What is the space complexity?