You have an array of n integers. You need to answer range queries (sum, min, max, GCD) on [l, r] and update individual elements, both in O(log n).

A Fenwick Tree handles sums and XOR in O(log n) because those operations are invertible: range(l, r) = prefix(r) - prefix(l - 1). But min, max, and GCD have no inverse. There is no way to "subtract" a minimum out of a prefix.

The segment tree solves this. It supports any associative operation in O(log n) per query and update, at the cost of more space and a few more lines of code.

The one requirement is that the operation be associative: merge(merge(a, b), c) == merge(a, merge(b, c)). This is what makes it safe to combine partial results from sibling subtrees in any order. Sum, min, max, GCD, XOR, and product are all associative. Average is not, which is why you compute sum and count separately and divide at the end.

The Problem

Given an array of n elements, we want to:

The naive approach answers queries in O(n) by scanning the range, and updates in O(1). If we have many queries, that O(n) per query adds up fast.

Precomputing a prefix sum gives us O(1) queries, but updates become O(n) because we have to rebuild the prefix array. We need both operations to be fast.

The Key Insight

Divide the array into segments recursively. Split the array in half, then split each half in half, and keep going until each segment contains a single element. Store the answer for each segment in a tree node. This gives us a binary tree where:

To answer a range query, we combine at most O(log n) nodes. To update an element, we change the leaf and propagate up through O(log n) ancestors.

A useful mental model is a tournament bracket: updating one player's result only requires replaying the matches on the path from that player to the final (the update path, O(log n) nodes), and finding the winner of a subset means combining the results of the matches that exactly cover that subset (the query decomposition, also O(log n) nodes).

Here is the segment tree for the array [2, 1, 5, 3, 4, 7] using range sum:

Each node stores the sum for its range. The root covers the entire array [0, 5] with sum 22. The leaves hold individual element values. Every internal node's value equals the sum of its two children.

Internal Representation

A segment tree is a binary tree stored in the heap-style array layout, with each node assigned an index that lets us derive its children from arithmetic alone:

How much space do we need?

A binary tree with n leaves has 2n - 1 nodes only when n is a power of 2. When it is not, the recursion still splits ranges until each leaf covers one element, but the resulting tree is no longer perfectly balanced and the heap-style array layout leaves gaps. The height is ceil(log2(n)), and the array can require up to 2^(ceil(log2(n)) + 1) positions, which can exceed 2n.

The safe upper bound is 4n, which works for any n. The extra space is constant overhead in exchange for a single allocation that always fits.

Build Operation

Building the tree is straightforward recursion. Start at the root, which covers the full range [0, n-1]. Split the range in half, build the left subtree for [start, mid] and the right subtree for [mid+1, end]. When start equals end, you have reached a leaf, so store the array value directly.

After recursion returns from both children, the parent node merges their results. For range sum, that means tree[node] = tree[2*node] + tree[2*node + 1]. The build runs in O(n) time: each used position in the tree array is visited at most once, and the total number of used positions is bounded by 4n.

Range Query

The range query is the operation that makes the segment tree worthwhile. Given a query range [l, r], we traverse the tree and classify each node's range [start, end] into one of three cases:

In this diagram, querying range [2, 4]:

The final answer is 5 + 7 = 12, which matches nums[2] + nums[3] + nums[4] = 5 + 3 + 4 = 12.

Why is this O(log n)? At each level of the tree, at most 4 nodes are visited (at most 2 partial overlaps that branch into children). Since the tree has O(log n) levels, the total work is O(log n).

Point Update

To update a single element, we descend from the root to the target leaf, then propagate the updated values back up. The recursion finds the leaf by checking whether the target index falls in the left or right child's range. Once the leaf is updated, each ancestor recalculates its value by merging its two children.

Updating index 2 from 5 to 6: the leaf node [2,2] changes from 5 to 6. Then [0,2] recalculates as 3 + 6 = 9 (was 8). Then [0,5] recalculates as 9 + 14 = 23 (was 22). Only nodes on the path from root to the target leaf are affected, so the update runs in O(log n).

Let us trace through a complete example with the array [2, 1, 5, 3, 4, 7] (6 elements, 0-indexed).

Step 1: Building the Segment Tree

The build process works bottom-up after the recursion reaches the leaves:

Step 2: Range Sum Query for [1, 4]

We want sum(1, 4) = nums[1] + nums[2] + nums[3] + nums[4] = 1 + 5 + 3 + 4 = 13.

The query correctly returns 13 by combining values from nodes [1,1], [2,2], and [3,4].

Step 3: Point Update, Change Index 2 from 5 to 6

Step 4: Verify with Range Query [1, 4] After Update

After updating index 2 to 6, the array is now [2, 1, 6, 3, 4, 7].

Expected: sum(1, 4) = 1 + 6 + 3 + 4 = 14.

Running the same query now returns 1 + 6 + 7 = 14 (node [1,1] returns 1, node [2,2] returns 6, node [3,4] returns 7). Correct.

Here is the full implementation. The merge operation is isolated into a single function, making it easy to swap sum for min, max, GCD, or any other associative operation.

Code Explanation

Let us walk through the key design decisions in the implementation.

The Merge Function

The merge function is the single point you change to support different operations. For range sum, it returns left + right. For range minimum, swap it to the language's min function. For GCD, use the language's gcd function. The rest of the code stays identical.

You also need to update the identity element in the query's no-overlap case. The identity element is the value that does not affect the result when merged:

This abstraction works because the operation is associative. The query decomposes the range into O(log n) disjoint segments and merges them, and associativity guarantees that the merge order does not change the answer. If you tried to use this with a non-associative operation (like subtraction), the partial results from siblings would combine incorrectly.

The Three Query Cases

The query function's logic is clean once you understand the three cases. The conditions right < start || end < left catch the no-overlap case. The condition left <= start && end <= right catches total overlap. Everything else is partial overlap, where we recurse into both children.

Every query is decomposed into at most O(log n) nodes whose ranges are fully contained in the query range, which is what gives the segment tree its logarithmic query time.

Build: O(n)

The tree has at most 4n nodes, and each node is visited exactly once during construction. The merge at each node is O(1), so the total build time is O(n).

Query: O(log n)

At each level of the tree, at most 4 nodes are visited. Here is the intuition: partial overlap can split into two children, but total overlap and no overlap are terminal. A more careful analysis shows that at most 2 partial overlap nodes exist per level (one at the left boundary and one at the right boundary of the query range). Since the tree has O(log n) levels, the total nodes visited is O(log n).

Update: O(log n)

The update follows a single path from root to leaf. The tree height is ceil(log2(n)), so the update visits O(log n) nodes and does O(1) work at each.

Space: O(n)

We allocate a 4n array. Although 4n > n, the space complexity is still O(n) since 4n is a constant multiple of n.

*Best case query happens when the root's range exactly matches the query range.

The basic segment tree we built is just the starting point. Several important variations exist for different scenarios.

Iterative Segment Tree (Bottom-Up)

The recursive version is clean and easy to understand, but function call overhead makes it slower in practice. An iterative segment tree uses a flat array of size 2n (not 4n) and works bottom-up. Leaves are stored at indices n through 2n-1. Internal nodes are computed by iterating from index n-1 down to 1. Queries and updates work by starting at the leaves and moving up.

The iterative version is faster in practice because it avoids the function call overhead of recursion, and it's the preferred form in competitive programming when constant factors matter. It is harder to extend with lazy propagation, and the index arithmetic is easy to get wrong if you haven't written it before. For a coding interview, stick with the recursive version unless you've rehearsed the iterative one to the point you can write it from memory without bugs.

Persistent Segment Tree

What if you need to answer queries about past versions of the array? A persistent segment tree creates a new version on each update by copying only the nodes on the path from root to the updated leaf (O(log n) nodes). All other nodes are shared between versions. This gives you O(log n) time per update and O(log n) space per version, with O(log n) queries on any version.

Dynamic Segment Tree

When the range of possible indices is huge (say, up to 10^9) but the number of actual elements is small, allocating a 4n array is wasteful. A dynamic segment tree creates nodes on demand, only materializing the parts of the tree that are actually needed. This is implemented using pointers instead of array indices.

Different Merge Operations

Swapping the merge function opens up a wide range of applications:

To switch operations, you only change two things: the merge function and the identity element returned in the no-overlap case. The tree structure, build, update, and query logic stay identical.

When should you reach for a segment tree versus a simpler structure?

*Segment tree with lazy propagation supports range update + range query in O(log n).

**Fenwick tree: supports range update + point query OR point update + range query in O(log n). Doing both simultaneously requires two BITs.

When to choose segment tree:

When NOT to use segment tree:

Pattern 1: Range Sum/Min/Max with Point Updates

This is the classic use case. Given an array, answer range aggregate queries while supporting element modifications. LeetCode 307 (Range Sum Query - Mutable) is the textbook example.

Pattern 2: Count of Elements in a Range (with Coordinate Compression)

Suppose you need to count how many elements in a subarray fall within a value range [lo, hi]. Build a segment tree over the value space (using coordinate compression if values are large). As you process elements, update the tree. This pattern appears in problems like "Count of Smaller Numbers After Self" (LeetCode 315).

Pattern 3: Interval and Geometry Problems

Problems involving intervals on a number line, like "Falling Squares" (LeetCode 699), use segment trees to track the maximum height at each position. The sweep-line technique combined with a segment tree solves many computational geometry problems efficiently.

But what if you need to update an entire range, not just a single element? Updating each point individually would cost O(n log n) for a range of n elements. Lazy propagation solves this in O(log n) by deferring updates until they are actually needed.