Segment Tree LeetCode Guide: The Range Query Template You Need

If you have been grinding LeetCode long enough, you have probably encountered a problem that asks you to compute range sums, range minimums, or range maximums on an array — and then update individual elements between queries. That is the exact scenario where a segment tree leetcode solution becomes essential.

For static arrays, prefix sums handle range queries in O(1) after O(n) preprocessing. But the moment the array becomes mutable — elements change between queries — prefix sums fall apart. Rebuilding the prefix sum after every update costs O(n), and that turns your efficient solution into a time limit exceeded verdict.

Segment trees solve this problem elegantly. They maintain a binary tree structure over array ranges, allowing both range queries and point updates in O(log n) time. They are overkill for most interview problems, but for the handful of Hard problems that require them, nothing else works.

This guide gives you a clean, reusable segment tree template that you can memorize for interviews. You will learn when to reach for a segment tree, how the data structure works internally, and which classic LeetCode problems require one.

The decision to use a segment tree comes down to one question: does the problem require both range queries and element updates? If the array never changes after it is built, simpler approaches almost always suffice. Prefix sums give you O(1) range sum queries. Sparse tables give you O(1) range minimum queries. No segment tree needed.

But when the problem says "update the value at index i" between queries, those static structures break down. Updating a prefix sum array requires O(n) work to rebuild. This is where the segment tree becomes the right tool — it handles both queries and updates in O(log n).

Here is the mental checklist. First, does the problem ask for an aggregate over a range — sum, minimum, maximum, or GCD? Second, does the array change during the process? If both answers are yes, a segment tree is almost certainly the intended solution.

A segment tree is a binary tree where each node represents a contiguous range of the original array. The root covers the entire array [0, n-1]. Its left child covers [0, mid] and its right child covers [mid+1, n-1], where mid is the midpoint. This recursive halving continues until each leaf node represents a single element.

Every internal node stores the aggregate value — sum, minimum, maximum, or whatever operation the problem requires — for its range. When you query a range [L, R], you traverse the tree and combine results from the nodes whose ranges overlap with your query range. Because the tree has O(log n) levels, this traversal takes O(log n) time.

Point updates work similarly. When you change an element at index i, you update the corresponding leaf and then propagate the change upward to every ancestor node. Since there are O(log n) ancestors, updates also take O(log n) time.

The build step visits every node exactly once, starting from the leaves and combining upward. With 2n - 1 total nodes for an array of size n, the build takes O(n) time. This gives you the classic segment tree complexity: Build O(n), query O(log n), update O(log n).

The cleanest segment tree implementation for interviews uses an array of size 2n, where n is the length of the input array. The leaves occupy positions n through 2n-1, and internal nodes occupy positions 1 through n-1. Position 0 is unused. This approach avoids the messier recursive implementation and is much easier to memorize.

The build step copies the input array into the leaf positions, then fills internal nodes bottom-up. For a sum segment tree, each internal node at position i stores tree[2*i] + tree[2*i+1]. For a min segment tree, it stores the minimum of its two children.

For a query on range [L, R], you start at the leaves (L + n and R + n) and walk upward. When L is a right child, its value contributes to the result and L moves right. When R is a left child, its value contributes and R moves left. You stop when L and R cross.

For a point update at index i, you update tree[i + n] with the new value and then walk upward, recomputing each parent as the combination of its two children. The entire update path is O(log n) nodes.

This iterative segment tree template is compact, efficient, and handles the vast majority of segment tree interview problems. Memorize it and you can adapt it to sum, min, max, or any associative operation.

The gold standard segment tree problem on LeetCode is Range Sum Query - Mutable (#307). You are given an integer array and need to support two operations: update a single element, and return the sum of elements in a given range. This is the textbook use case for a segment tree — mutable array with range sum queries. If you can solve this one cleanly, you have the core template down.

Count of Smaller Numbers After Self (#315) is a harder application. For each element in the array, you need to count how many elements to its right are smaller. The segment tree approach processes the array from right to left, using the tree to track the count of elements seen so far in each value range. Each query asks "how many values less than current have I already seen?" — a range query on value frequencies.

The Skyline Problem (#218) is a classic Hard that can be solved with a segment tree, though most interviewers accept a priority queue approach. The segment tree solution processes building events and maintains maximum heights across coordinate ranges. It demonstrates how segment trees apply beyond simple sum and min queries.

These three problems cover the core segment tree patterns you will see in interviews: direct range aggregation (#307), order statistics via frequency tracking (#315), and geometric range queries (#218). Master #307 first, then attempt #315.

Standard segment trees handle point updates — changing one element at a time. But some problems require range updates: add a value to every element in [L, R], then query a range sum. Without optimization, a range update on k elements costs O(k log n), which is too slow for large inputs.

Lazy propagation solves this by deferring updates. Instead of immediately pushing a range update all the way to the leaves, you mark the affected nodes with a "lazy" tag that records the pending update. When a future query or update needs to access a node's children, you push the lazy tag down at that point.

The key insight is that you only push updates down when you actually need the children's values. This means a range update touches O(log n) nodes instead of O(k), and the deferred work is amortized across future operations. Both range updates and range queries remain O(log n).

Lazy propagation is almost exclusively a competitive programming technique. In real coding interviews, even at top companies, you are extremely unlikely to encounter a problem that requires lazy propagation. The basic segment tree with point updates covers every realistic interview scenario. Learn lazy propagation only if you are targeting competitive programming or have already mastered every other pattern.

Start your segment tree practice with Range Sum Query - Mutable (#307). Implement the iterative array-based template from scratch, without looking at references. If you can write the build, query, and update functions from memory in under ten minutes, you are ready for any segment tree problem that appears in an interview.

Once you are comfortable with #307, attempt Count of Smaller Numbers After Self (#315). This problem forces you to think about what the segment tree is tracking — not the original array values but frequency counts. It tests whether you truly understand the data structure or just memorized one application.

Keep perspective on where segment trees fit in interview prep. They appear in roughly 2-3% of coding interview questions, almost exclusively at the Hard level. If you are still working on mastering arrays, hash maps, trees, and dynamic programming, those patterns will give you far more return on your study time.

When you encounter a range query problem in an interview, always consider simpler approaches first. Prefix sums handle static arrays. Binary indexed trees (Fenwick trees) are simpler to implement for point updates with prefix queries. Only reach for a segment tree when the problem explicitly requires range queries on a mutable array with operations that a BIT cannot handle.

Review segment tree problems with YeetCode flashcards to build the pattern recognition that helps you identify when a segment tree is the right tool — and more importantly, when it is not. The best interview performance comes from choosing the simplest data structure that solves the problem.