Introduction to Segment Trees

March 2026 · 20 min read

Segment trees are one of the most powerful data structures in competitive programming and systems design. They solve a deceptively simple problem, answering range queries efficiently while also supporting updates, but the idea behind them is elegant and worth understanding deeply.

This post builds the foundation. We'll understand why segment trees exist, what problem they solve that simpler approaches can't, and how the tree structure maps to the array. By the end, you'll be able to draw a segment tree from any array and understand exactly what each node represents.

The Range Query Problem

Imagine you have an array of numbers:

arr = [1, 3, 5, 7, 9, 11, 2, 4]

And you need to repeatedly answer questions like:

• "What is the sum of elements from index 2 to index 5?" → 5 + 7 + 9 + 11 = 32
• "What is the minimum element from index 0 to index 3?" → min(1, 3, 5, 7) = 1
• "What is the GCD of elements from index 4 to index 7?" → gcd(9, 11, 2, 4) = 1

These are range queries: given two indices l and r, compute some aggregate function over the sub-array arr[l..r].

The Naive Approach

Loop from l to r, accumulate the result. Each query takes O(n) in the worst case (when the range spans the entire array). Updates are instant, just change arr[i] in O(1).

If you have Q queries on an array of size n, the total time is O(Q · n). For n = 105 and Q = 105, that's 10¹⁰ operations, way too slow.

Prefix Sums

Precompute a prefix sum array: prefix[i] = arr[0] + arr[1] + ... + arr[i]. Then sum(l, r) = prefix[r] - prefix[l-1] in O(1).

But there's a catch: if an element changes (arr[i] = newVal), you must rebuild all of prefix[i..n-1], that's O(n) per update. If updates are frequent, prefix sums fall apart.

The Core Trade-off

Segment trees hit the sweet spot: both queries and updates are O(log n). This makes them ideal when you have a mix of thousands of queries and updates.

The Structure: Divide and Conquer on Ranges

The idea is beautifully simple: recursively split the array in half and store the aggregate of each half.

Start with the full array [0, n-1]. Split it into [0, mid] and [mid+1, n-1] where mid = (0 + n-1) / 2. Recursively split each half until you reach individual elements. Store the aggregate (e.g., sum) at each level.

Building from the Array

Let's build a segment tree for arr = [1, 3, 5, 7, 9, 11, 2, 4]:

1. Level 3 (leaves): Each leaf holds one element. arr[0]=1, arr[1]=3, arr[2]=5, ..., arr[7]=4.
2. Level 2: Combine pairs. [0-1]=1+3=4, [2-3]=5+7=12, [4-5]=9+11=20, [6-7]=2+4=6.
3. Level 1: Combine again. [0-3]=4+12=16, [4-7]=20+6=26.
4. Level 0 (root): [0-7]=16+26=42. This is the sum of the entire array.

What Each Node Represents

Every node in the tree represents a contiguous sub-range of the original array:

• The root represents the entire array [0, n-1].
• Each internal node splits its range into two halves: [start, mid] for the left child and [mid+1, end] for the right child.
• Each leaf represents one single element [i, i].
• Every node stores the aggregate (sum, min, max, etc.) of all elements in its range.

This means: to find the sum of any range [l, r], we don't need to look at every element. We just need to find nodes whose ranges together cover [l, r] exactly, and there are at most O(log n) such nodes.

Why O(log n)? The Intuition

Why queries are fast

Consider querying sum(2, 5) on our example tree. We start at the root [0-7]. Its range isn't fully inside [2, 5], so we go to both children. The left child [0-3] partially overlaps, we recurse. The right child [4-7] partially overlaps, we recurse there too.

But here's the key: at each level of the tree, at most 2 nodes are "partially overlapping" (one on the left boundary, one on the right boundary). All other nodes are either fully inside (we take their value immediately) or fully outside (we skip them). Since the tree has O(log n) levels, we visit at most O(log n) nodes.

Why updates are fast

When arr[i] changes, only nodes whose range contains index i need updating. Starting from the root, there's exactly one path down to the leaf at index i, every other node's range either doesn't contain i (skip) or is on this single path. The path has length O(log n), so only O(log n) nodes need recalculating.

Storing the Tree in an Array

We don't use pointer-based nodes for segment trees. Instead, we use an array with 1-based indexing, exactly like a binary heap:

• The root is at index 1.
• For a node at index i, its left child is at 2*i and right child is at 2*i + 1.
• The parent of node i is at i / 2 (integer division).

Why Does This Formula Work?

Write each node’s index in binary. The pattern is immediate:

• Root = index 1 = binary 1.
• Go left = multiply by 2 = append a 0 bit. Index 1 → 10 = 2.
• Go right = multiply by 2 + 1 = append a 1 bit. Index 1 → 11 = 3.

That’s literally what ×2 and ×2+1 do in binary: shift left and append a bit. So every node’s index is 1 followed by its path from the root, where 0 = left and 1 = right:

Going to a child = appending one more bit to the path. Multiplying by 2 appends 0 (left child), adding 1 flips that last bit to 1 (right child). The formula is binary arithmetic on tree paths. That’s all there is to it.

How much space do we need?

For an array of size n, we store the segment tree in a flat array. But how big must that array be? The answer is 4n. Here's the step-by-step reasoning:

Case 1: n is a power of 2

When n = 2^k, the tree is a perfect binary tree. Every level is completely filled.

• Level 0 (root): 1 node
• Level 1: 2 nodes
• Level 2: 4 nodes
• …
• Level k (leaves): n nodes

The total node count is the sum of every level: 1 + 2 + 4 + … + n. This is a geometric progression (each term is double the previous one), so we can use the standard GP sum formula.

Two things make this click. First, there are k + 1 levels, not k: the root is level 0 and the leaves are level k, so counting both endpoints gives k + 1 terms. Second, the intuition behind 1 + 2 + 4 + … + 2k = 2k+1 − 1 is that doubling and adding one always reaches the next power of two: 1 + 1 = 2, 2 + 2 = 4, and in general the sum of all the smaller powers is exactly one less than the next power. In binary it is just k + 1 ones (e.g. 1111₂ = 15 = 24 − 1).

So total nodes = 2n − 1. Since we use 1-based indexing (root at index 1), the largest index is 2n − 1 and we need an array of size 2n. Clean and tight.

Case 2: n is NOT a power of 2 — the tricky case

When n isn't a power of 2, the tree is not perfectly balanced. Some branches go one level deeper than others. The problem: a node at a deep level might have a high array index even though there are few total nodes.

Here's what happens visually. Node 1 splits [0–4] into [0–2] and [3–4]. The left subtree [0–2] splits into [0–1] and [2], and [0–1] splits again into leaves [0] and [1]. That path is 3 edges deep, making the leaves land at indices 8 and 9 — well beyond 2n = 10's safe range for child computations at index 5 (children would be 10 and 11).

The safe formula: allocate 4n

Here is the clean argument for why 4n always works. The build recursion keeps splitting a range in half until every leaf covers a single element, so the tree has depth d = ⌈log2(n)⌉ (root at depth 0). With 1-based heap indexing a node at index i has children 2i and 2i+1, so the index roughly doubles every time we descend one level.

The clean way to bound the largest index is to round n up to the next power of two, call it N = 2⌈log2(n)⌉. A segment tree drawn over N leaves is a perfect binary tree with 2N − 1 nodes, and its deepest leaves occupy heap indices N through 2N − 1. Any real segment tree over n ≤ N elements is a subset of that shape, so the largest index it can ever touch is at most 2N − 1.

That is the whole proof: every index the tree can possibly use is strictly less than 4n, so an array of size 4n can never overflow, for any n. Note the space is still O(n) asymptotically; the 4 is just the constant factor you must actually allocate to stay safe.

vector<int> tree(4 * n);  // always safe, never overflows

Here's the mapping for our 8-element array (which is a power of 2, so the tree is perfect):

Beyond Sums: Any Associative Operation

Segment trees aren't limited to sums. They work for any associative operation, one where merge(merge(a, b), c) = merge(a, merge(b, c)):

The tree structure stays exactly the same. Only the merge function and identity element change. The rest of this series uses sum as the running example, but everything generalizes.

When to Use a Segment Tree

Use a segment tree when:

• You need both range queries and updates on the same array.
• The aggregate operation is associative (sum, min, max, GCD, XOR, etc.).
• The number of queries + updates is large (10⁴ or more).
• You need guaranteed O(log n) per operation, not amortized.

Don't use a segment tree when:

• No updates: Use prefix sums (O(1) query, simpler code).
• No queries: Just use the array directly.
• Only point queries: A regular array works fine.
• Simpler alternative exists: For some problems, a binary heap or monotonic stack suffices.

Segment Tree vs. Other Structures

* Range update with lazy propagation (covered in a later post).

What's Coming Next

This series covers segment trees from the ground up:

1. This post: Why segment trees exist, the structure, array representation.
2. Building & Querying: How the build algorithm works, how range queries decompose into O(log n) nodes, with step-by-step animations.
3. Updates: Point updates, how changes propagate up, and the transition to range updates.
4. Lazy Propagation: The key technique that makes range updates O(log n). Explained in extreme detail with animations.
5. Patterns & Practice: Common segment tree problems, variations (min/max/GCD), and interview-ready templates.

Summary

• The range query problem: answer aggregate queries on sub-arrays while supporting updates.
• Brute force is O(n) per query. Prefix sums are O(1) query but O(n) update. Segment trees are O(log n) for both.
• A segment tree is a binary tree where each node stores the aggregate of a contiguous range. The root covers the full array; leaves cover individual elements.
• The tree is stored in a flat array with 1-based indexing: node i's children are 2i and 2i+1.
• Allocate 4n space to handle non-power-of-2 sizes safely.
• Works for any associative operation: sum, min, max, GCD, XOR, product, etc.
• Queries are fast because at each tree level, at most 2 nodes are at the range boundary, the rest are either fully inside or fully outside.
• Updates are fast because only O(log n) nodes (one path from leaf to root) are affected.