Segment Tree for Range Queries: A Practical Interview Guide

Why segment trees matter in interviews

Range query problems show up everywhere: sums over subarrays, minimums in a range, counting frequencies, and updates that change the array over time. A brute-force scan is often too slow once the input grows or when queries and updates are mixed together.

That is where a segment tree becomes useful. It gives you a way to answer many range queries quickly while still supporting updates efficiently. In interviews, it is a strong signal that you can choose the right data structure when the problem has both query and update operations.

The main idea is simple: precompute answers for chunks of the array, then combine those chunks on demand. Once you understand the tree structure, the rest is mostly about practicing the recursive pattern.

Problem statement

A segment tree is a data structure built over an array to support operations like:

• range query(l, r): ask for sum / min / max / gcd / count over a subarray
• point update(i, val): change one element
• range update(l, r, delta): change many elements in one shot, often with lazy propagation

Typical interview variants include:

• Range sum query with point update
• Range minimum query
• Count how many values in a range satisfy some condition
• Range add update with range sum query

If you solve these with direct iteration, each query costs O(n) in the worst case. If there are many queries, that becomes too slow.

Intuition and insight

A segment tree works because many range queries can be decomposed into smaller ranges.

Imagine your array has 8 elements. Instead of storing only the original values, you store aggregated answers for:

• each single element
• each pair
• each block of 4
• the whole array

Each node in the tree represents a range [l, r] and stores the answer for that range. The parent node combines the results of its children.

For example, if the tree stores range sums:

• leaf node [i, i] stores arr[i]
• internal node [l, r] stores left_sum + right_sum

When you query a range, you do not inspect every element. You only visit the nodes whose ranges overlap the query.

Why this helps

For a balanced segment tree:

• building takes O(n)
• a query takes O(log n)
• a point update takes O(log n)

That is the key interview win: instead of scanning the whole array, you jump through a logarithmic number of segments.

Approach walkthrough

Let’s start with the simplest useful version: range sum query with point update.

1) Build the tree

We use an array-backed tree. A common implementation uses a list of size 4 * n, which is enough for a binary tree representation.

Each recursive call handles a segment [l, r].

• If l == r, store the array value at the leaf
• Otherwise, split into [l, mid] and [mid+1, r]
• Store the combination of the two children

2) Query a range

When asked for the sum over [ql, qr]:

• if the current segment is completely outside the query range, return 0
• if it is completely inside, return the stored sum
• otherwise, query both children and combine their answers

3) Update one point

To update arr[idx] = val:

• descend the tree to the leaf representing idx
• update the leaf
• recompute values on the path back up

Example 1: range sum query with point update

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1)

    def build(self, node, l, r):
        if l == r:
            self.tree[node] = self.arr[l]
            return
        mid = (l + r) // 2
        self.build(node * 2, l, mid)
        self.build(node * 2 + 1, mid + 1, r)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, node, l, r, ql, qr):
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        left_sum = self.query(node * 2, l, mid, ql, qr)
        right_sum = self.query(node * 2 + 1, mid + 1, r, ql, qr)
        return left_sum + right_sum

    def update(self, node, l, r, idx, val):
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid:
            self.update(node * 2, l, mid, idx, val)
        else:
            self.update(node * 2 + 1, mid + 1, r, idx, val)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

How to use it

arr = [2, 1, 5, 3, 4]
st = SegmentTree(arr)

print(st.query(1, 0, st.n - 1, 1, 3))  # 1 + 5 + 3 = 9
st.update(1, 0, st.n - 1, 2, 10)      # arr[2] = 10
print(st.query(1, 0, st.n - 1, 1, 3))  # 1 + 10 + 3 = 14

What is happening

• The first query asks for indices 1..3
• The tree combines only the relevant ranges
• The update changes one leaf and fixes the sums above it

This is the core segment tree pattern you need to recognize in interviews.

Example 2: range minimum query

A segment tree is not limited to sums. You can store any associative operation, such as min.

class MinSegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [float('inf')] * (4 * self.n)
        self.build(1, 0, self.n - 1)

    def build(self, node, l, r):
        if l == r:
            self.tree[node] = self.arr[l]
            return
        mid = (l + r) // 2
        self.build(node * 2, l, mid)
        self.build(node * 2 + 1, mid + 1, r)
        self.tree[node] = min(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, node, l, r, ql, qr):
        if qr < l or r < ql:
            return float('inf')
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return min(
            self.query(node * 2, l, mid, ql, qr),
            self.query(node * 2 + 1, mid + 1, r, ql, qr)
        )

Example usage

arr = [7, 2, 6, 3, 1, 5]
st = MinSegmentTree(arr)
print(st.query(1, 0, st.n - 1, 1, 4))  # min of [2, 6, 3, 1] = 1
print(st.query(1, 0, st.n - 1, 0, 2))  # min of [7, 2, 6] = 2

The query logic stays the same. Only the merge operation changes from + to min, and the identity value changes from 0 to inf.

Example 3: range update with lazy propagation

Point updates are easy. Range updates are where segment trees get more powerful.

Suppose you want to add delta to every value in a range [l, r], and still answer range sum queries.

If you update each element directly, that could take O(n) per update. Lazy propagation fixes this by delaying work.

Lazy propagation idea

If a node fully covers the update range:

• update the node’s stored aggregate immediately
• mark the update as “pending” in a lazy array
• push the pending update to children only when needed

This lets you keep updates and queries efficient.

class LazySegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1)

    def build(self, node, l, r):
        if l == r:
            self.tree[node] = self.arr[l]
            return
        mid = (l + r) // 2
        self.build(node * 2, l, mid)
        self.build(node * 2 + 1, mid + 1, r)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def push(self, node, l, r):
        if self.lazy[node] == 0:
            return
        pending = self.lazy[node]
        self.tree[node] += pending * (r - l + 1)
        if l != r:
            self.lazy[node * 2] += pending
            self.lazy[node * 2 + 1] += pending
        self.lazy[node] = 0

    def range_add(self, node, l, r, ql, qr, delta):
        self.push(node, l, r)
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.lazy[node] += delta
            self.push(node, l, r)
            return
        mid = (l + r) // 2
        self.range_add(node * 2, l, mid, ql, qr, delta)
        self.range_add(node * 2 + 1, mid + 1, r, ql, qr, delta)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def range_sum(self, node, l, r, ql, qr):
        self.push(node, l, r)
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self.range_sum(node * 2, l, mid, ql, qr) + \
               self.range_sum(node * 2 + 1, mid + 1, r, ql, qr)

Example usage

arr = [1, 2, 3, 4, 5]
st = LazySegmentTree(arr)

print(st.range_sum(1, 0, st.n - 1, 0, 4))  # 15
st.range_add(1, 0, st.n - 1, 1, 3, 10)      # [1, 12, 13, 14, 5]
print(st.range_sum(1, 0, st.n - 1, 0, 4))  # 45
print(st.range_sum(1, 0, st.n - 1, 2, 3))  # 27

Why lazy propagation works

The node covering [1, 3] does not need to push changes all the way to the leaves right away. It can store the total effect of the update and defer the rest until a query or deeper update requires it.

That is the difference between a fast tree and a slow one when range updates are involved.

Step-by-step mental model for interviews

When you see a segment tree problem, ask:

• What operation do I need to answer on a range?
• Is the operation associative? If yes, a segment tree may work.
• Do I need point updates or range updates?
• Can I define an identity value for “no overlap”?

Then map the problem into three recursive functions:

• build
• query
• update or range_update

Common identities

• Sum: 0
• Minimum: inf
• Maximum: -inf
• Product: 1

If your merge function is combine(left, right), the tree can usually support it as long as combine is associative.

Complexity analysis

Here is a practical comparison of common approaches:

Memory

A segment tree usually needs O(4n) space, which is acceptable in most interview settings.

Common pitfalls

• Forgetting the identity value for non-overlapping segments
• Using a non-associative operation incorrectly
• Not pushing lazy values before querying or descending
• Mixing inclusive and exclusive range conventions
• Off-by-one errors in recursive splits

A good habit is to keep your whole implementation on inclusive ranges [l, r] and stay consistent.

Related problems

Segment trees are useful for more than sums and minimums. Once you understand the pattern, you can adapt it to:

• range maximum query
• count of values in a range
• number of distinct elements with coordinate compression or richer nodes
• merge intervals with custom node metadata
• histogram and maximum subarray style problems with advanced node state

You may also encounter persistent segment trees or iterative segment trees, but the recursive version is the best starting point for interviews.

Key takeaways

• Segment trees support fast range queries on arrays that change over time.
• The tree stores aggregated answers for intervals, not individual values only.
• Point updates are straightforward; range updates usually need lazy propagation.
• The core interview skill is recognizing when a query can be broken into smaller disjoint segments.
• If the operation is associative, a segment tree is often worth considering.

If you want to see the variables update live as you step through, check out codebrew.ai.

Practice these next

1. Range Sum Query - Mutable
2. Range Minimum Query
3. Falling Squares
4. My Calendar III
5. Count of Smaller Numbers After Self