Interview Guide: Segment Trees Problems and Solutions

Segment Trees: A Complete Interview Guide

What Is a Segment Tree?

A segment tree is a binary tree data structure that stores information about intervals (segments) of an array. It allows you to answer range queries and perform point updates in O(log n) time, compared to the O(n) time required by a naive array scan. The tree is built over an array of n elements, and each node in the segment tree represents a contiguous subarray, storing some aggregate value for that segment — such as sum, minimum, maximum, greatest common divisor, or any associative operation.

The classic segment tree is a full binary tree where leaf nodes correspond to individual array elements, and internal nodes represent the merged result of their two children. The root node covers the entire array from index 0 to n-1.

Visually, for an array [5, 3, 7, 1, 9, 2], the segment tree looks like this:

                    [0-5]: sum=27
                 /                  \
        [0-2]: sum=15              [3-5]: sum=12
       /           \              /           \
 [0-1]: sum=8   [2]: 7     [3-4]: sum=10   [5]: 2
   /       \               /       \
[0]:5    [1]:3          [3]:1    [4]:9

Why Segment Trees Matter in Interviews

Segment trees appear frequently in coding interviews — especially at top-tier companies — because they test a candidate's understanding of:

• Divide-and-conquer thinking — recursively splitting problems into smaller subproblems
• Tree data structures — representing hierarchical relationships in arrays
• Lazy propagation — deferring work to optimize range updates
• Time complexity analysis — recognizing when O(log n) solutions are required
• Associative operations — understanding which merge functions work with the structure

Common interview problems that leverage segment trees include range sum queries, range minimum queries with updates, counting inversions in ranges, finding the k-th zero in a binary array, and handling complex range updates like "add value to range" or "set range to value."

How to Build a Segment Tree

There are two standard approaches: the array-based (iterative) representation and the pointer-based (recursive) representation. For interviews, the array-based version is more common because it is compact, cache-friendly, and easier to debug under pressure.

Step 1: Understand the Array Representation

We allocate an array tree of size 4 * n (a safe upper bound for a full binary tree with n leaves). The root is at index 1, and for any node at index i:

• Left child: 2 * i
• Right child: 2 * i + 1
• Parent: i / 2

Each node stores the aggregate value for its segment. Leaves correspond to original array elements.

Step 2: Build Function (Recursive)

The build function recursively constructs the tree from the original array. It takes the node index, the segment boundaries [left, right], and populates tree[node] with the computed value.

def build(node, left, right, arr, tree):
    """
    Builds the segment tree recursively.
    node: current tree index (root = 1)
    left, right: segment boundaries in the original array (inclusive)
    arr: original input array
    tree: segment tree array (size 4*n)
    """
    if left == right:
        # Leaf node: store the actual array element
        tree[node] = arr[left]
        return
    
    mid = (left + right) // 2
    # Build left subtree
    build(2 * node, left, mid, arr, tree)
    # Build right subtree
    build(2 * node + 1, mid + 1, right, arr, tree)
    
    # Merge: sum of children (change this for min/max/gcd)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

For an array arr = [5, 3, 7, 1, 9, 2], you would call build(1, 0, len(arr)-1, arr, tree) with tree allocated as [0] * (4 * len(arr)).

Step 3: Point Update

To update a single element at position pos to a new value val, we traverse from the root down to the leaf, updating all ancestors along the path.

def update(node, left, right, pos, val, tree):
    """
    Updates arr[pos] = val and propagates changes up the tree.
    """
    if left == right:
        # Leaf node reached
        tree[node] = val
        return
    
    mid = (left + right) // 2
    if pos <= mid:
        update(2 * node, left, mid, pos, val, tree)
    else:
        update(2 * node + 1, mid + 1, right, pos, val, tree)
    
    # Recompute current node after child update
    tree[node] = tree[2 * node] + tree[2 * node + 1]

Time complexity: O(log n) — we only visit one path from root to leaf.

Step 4: Range Query

A range query asks for the aggregate value over [ql, qr]. The algorithm traverses the tree and collects results from nodes that are completely inside the query range. If a node's segment is completely outside the query range, it is ignored. If it partially overlaps, we recurse into both children.

def query(node, left, right, ql, qr, tree):
    """
    Returns the aggregate for arr[ql..qr].
    """
    # Case 1: No overlap
    if ql > right or qr < left:
        return 0  # Identity element for sum (0 for sum, -inf for max, inf for min)
    
    # Case 2: Complete overlap — node's segment is fully inside query range
    if ql <= left and right <= qr:
        return tree[node]
    
    # Case 3: Partial overlap — query both sides
    mid = (left + right) // 2
    left_result = query(2 * node, left, mid, ql, qr, tree)
    right_result = query(2 * node + 1, mid + 1, right, ql, qr, tree)
    
    return left_result + right_result  # Merge operation

Time complexity: O(log n) in the worst case — we visit at most 4 log n nodes.

Putting It All Together: Complete Example

Here is a full working example of a segment tree for range sum queries and point updates in Python:

class SegmentTreeSum:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1, arr)
    
    def build(self, node, left, right, arr):
        if left == right:
            self.tree[node] = arr[left]
            return
        mid = (left + right) // 2
        self.build(2 * node, left, mid, arr)
        self.build(2 * node + 1, mid + 1, right, arr)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def update(self, pos, val):
        self._update(1, 0, self.n - 1, pos, val)
    
    def _update(self, node, left, right, pos, val):
        if left == right:
            self.tree[node] = val
            return
        mid = (left + right) // 2
        if pos <= mid:
            self._update(2 * node, left, mid, pos, val)
        else:
            self._update(2 * node + 1, mid + 1, right, pos, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)
    
    def _query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return 0  # identity for sum
        if ql <= left and right <= qr:
            return self.tree[node]
        mid = (left + right) // 2
        left_val = self._query(2 * node, left, mid, ql, qr)
        right_val = self._query(2 * node + 1, mid + 1, right, ql, qr)
        return left_val + right_val

# Usage
arr = [5, 3, 7, 1, 9, 2]
st = SegmentTreeSum(arr)
print(st.query(0, 5))   # Sum of entire array -> 27
print(st.query(1, 3))   # Sum of arr[1..3] -> 3+7+1 = 11
st.update(2, 10)        # Change arr[2] from 7 to 10
print(st.query(0, 5))   # New total -> 30

Lazy Propagation: Handling Range Updates

When you need to update an entire range [l, r] by adding a value (or setting a value), visiting every leaf individually would take O(n log n). Lazy propagation defers updates by storing pending changes in a separate lazy array. When a node's segment is completely inside the update range, we update the node's value and mark its lazy entry — without traversing further. The lazy value is only pushed down to children when we later need to visit them for a query or another update.

Lazy Range Update Example (Addition)

class SegmentTreeLazy:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)  # pending additions
        self.build(1, 0, self.n - 1, arr)
    
    def build(self, node, left, right, arr):
        if left == right:
            self.tree[node] = arr[left]
            return
        mid = (left + right) // 2
        self.build(2 * node, left, mid, arr)
        self.build(2 * node + 1, mid + 1, right, arr)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def push_down(self, node, left, right):
        """
        Propagate lazy value from current node to its children.
        """
        if self.lazy[node] == 0:
            return
        mid = (left + right) // 2
        
        # Apply lazy to left child
        self.tree[2 * node] += self.lazy[node] * (mid - left + 1)
        self.lazy[2 * node] += self.lazy[node]
        
        # Apply lazy to right child
        self.tree[2 * node + 1] += self.lazy[node] * (right - mid)
        self.lazy[2 * node + 1] += self.lazy[node]
        
        # Clear lazy at current node
        self.lazy[node] = 0
    
    def range_update(self, ul, ur, val):
        self._range_update(1, 0, self.n - 1, ul, ur, val)
    
    def _range_update(self, node, left, right, ul, ur, val):
        # No overlap
        if ul > right or ur < left:
            return
        
        # Complete overlap: apply lazy and stop
        if ul <= left and right <= ur:
            self.tree[node] += val * (right - left + 1)
            self.lazy[node] += val
            return
        
        # Partial overlap: push down and recurse
        self.push_down(node, left, right)
        mid = (left + right) // 2
        self._range_update(2 * node, left, mid, ul, ur, val)
        self._range_update(2 * node + 1, mid + 1, right, ul, ur, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)
    
    def _query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return 0
        if ql <= left and right <= qr:
            return self.tree[node]
        # Must push down before recursing
        self.push_down(node, left, right)
        mid = (left + right) // 2
        left_val = self._query(2 * node, left, mid, ql, qr)
        right_val = self._query(2 * node + 1, mid + 1, right, ql, qr)
        return left_val + right_val

# Usage
arr = [1, 2, 3, 4, 5]
st = SegmentTreeLazy(arr)
st.range_update(1, 3, 5)   # Add 5 to arr[1..3] -> arr becomes [1,7,8,9,5]
print(st.query(0, 4))      # Total: 1+7+8+9+5 = 30
print(st.query(1, 3))      # 7+8+9 = 24

The key insight: push_down is called whenever we need to access children — ensuring that pending updates are applied before we read or modify subtree values. This keeps the O(log n) complexity for both range updates and queries.

Common Interview Problems and Solutions

Problem 1: Range Minimum Query (RMQ) with Updates

Instead of sum, store the minimum value in each node. The identity element for minimum is positive infinity (float('inf')). The merge operation becomes min(left_child, right_child).

class SegmentTreeMin:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [float('inf')] * (4 * self.n)
        self.build(1, 0, self.n - 1, arr)
    
    def build(self, node, left, right, arr):
        if left == right:
            self.tree[node] = arr[left]
            return
        mid = (left + right) // 2
        self.build(2 * node, left, mid, arr)
        self.build(2 * node + 1, mid + 1, right, arr)
        self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
    
    def update(self, pos, val):
        self._update(1, 0, self.n - 1, pos, val)
    
    def _update(self, node, left, right, pos, val):
        if left == right:
            self.tree[node] = val
            return
        mid = (left + right) // 2
        if pos <= mid:
            self._update(2 * node, left, mid, pos, val)
        else:
            self._update(2 * node + 1, mid + 1, right, pos, val)
        self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
    
    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)
    
    def _query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return float('inf')
        if ql <= left and right <= qr:
            return self.tree[node]
        mid = (left + right) // 2
        left_min = self._query(2 * node, left, mid, ql, qr)
        right_min = self._query(2 * node + 1, mid + 1, right, ql, qr)
        return min(left_min, right_min)

Problem 2: Range Maximum Query with Updates

Identical to RMQ but using max() and identity element float('-inf') for out-of-range returns.

class SegmentTreeMax:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [float('-inf')] * (4 * self.n)
        self.build(1, 0, self.n - 1, arr)
    
    def build(self, node, left, right, arr):
        if left == right:
            self.tree[node] = arr[left]
            return
        mid = (left + right) // 2
        self.build(2 * node, left, mid, arr)
        self.build(2 * node + 1, mid + 1, right, arr)
        self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])
    
    def update(self, pos, val):
        self._update(1, 0, self.n - 1, pos, val)
    
    def _update(self, node, left, right, pos, val):
        if left == right:
            self.tree[node] = val
            return
        mid = (left + right) // 2
        if pos <= mid:
            self._update(2 * node, left, mid, pos, val)
        else:
            self._update(2 * node + 1, mid + 1, right, pos, val)
        self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])
    
    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)
    
    def _query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return float('-inf')
        if ql <= left and right <= qr:
            return self.tree[node]
        mid = (left + right) // 2
        left_max = self._query(2 * node, left, mid, ql, qr)
        right_max = self._query(2 * node + 1, mid + 1, right, ql, qr)
        return max(left_max, right_max)

Problem 3: Counting the Number of Zeros in a Range

Store the count of zeros in each segment. The identity element is 0. Build from an array where each position is 1 if arr[i] == 0 else 0. This pattern extends to counting any specific value.

class SegmentTreeZeroCount:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        # Convert array: 1 if zero, else 0
        zero_arr = [1 if x == 0 else 0 for x in arr]
        self.build(1, 0, self.n - 1, zero_arr)
    
    def build(self, node, left, right, zero_arr):
        if left == right:
            self.tree[node] = zero_arr[left]
            return
        mid = (left + right) // 2
        self.build(2 * node, left, mid, zero_arr)
        self.build(2 * node + 1, mid + 1, right, zero_arr)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def update(self, pos, new_val):
        # Update: set leaf to 1 if new_val is 0, else 0
        self._update(1, 0, self.n - 1, pos, 1 if new_val == 0 else 0)
    
    def _update(self, node, left, right, pos, val):
        if left == right:
            self.tree[node] = val
            return
        mid = (left + right) // 2
        if pos <= mid:
            self._update(2 * node, left, mid, pos, val)
        else:
            self._update(2 * node + 1, mid + 1, right, pos, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)
    
    def _query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return 0
        if ql <= left and right <= qr:
            return self.tree[node]
        mid = (left + right) // 2
        return (self._query(2 * node, left, mid, ql, qr) +
                self._query(2 * node + 1, mid + 1, right, ql, qr))

Problem 4: Finding the k-th Element (Order Statistics)

You can use a segment tree to find the k-th occurrence of a value (e.g., k-th 1 in a binary array, or k-th smallest element in a frequency array). The tree stores counts. To find the k-th element, traverse from root: if the left child's count is ≥ k, go left; otherwise subtract left's count from k and go right.

def find_kth(node, left, right, k, tree):
    """
    Returns the index of the k-th 1 in the array (1-indexed k).
    Assumes tree stores count of 1s in each segment.
    """
    if left == right:
        return left  # leaf index
    
    mid = (left + right) // 2
    left_count = tree[2 * node]
    
    if k <= left_count:
        return find_kth(2 * node, left, mid, k, tree)
    else:
        return find_kth(2 * node + 1, mid + 1, right, k - left_count, tree)

# Usage: call find_kth(1, 0, n-1, k, tree)

Best Practices for Segment Tree Interviews

• Master the array representation — It is faster to code and less error-prone than pointer-based trees. Use 4*n as the safe tree size.
• Always define your identity element clearly — For sum it's 0, for min it's ∞, for max it's -∞, for product it's 1. Return this when there is no overlap in a query.
• Draw the tree for small examples — Before coding, sketch the tree for n=4 or n=6. Label node indices and segment ranges. This prevents off-by-one errors.
• Use 0-based or 1-based indexing consistently — In the array, use 0-based indexing for left/right boundaries. For the tree, start the root at index 1. Be explicit in your comments.
• Practice the three core operations until they become muscle memory — Build, point update, range query. If you can write these from scratch in 10 minutes, you are ready.
• Understand when to push lazy values — Push down before any recursive descent in a query or update. Clear lazy after propagating. Multiply lazy value by segment length for sum-based trees.
• Test with edge cases — Single-element arrays, query spanning the whole array, query with ql == qr, updates that don't change values, and out-of-bounds queries (though most problems guarantee valid inputs).
• Know your merge operation's properties — Segment trees work for any associative operation (sum, min, max, gcd, product). They do not directly support non-associative operations like matrix multiplication order-sensitive queries without adaptation.
• Consider iterative segment trees for speed — Once comfortable with recursion, learn the iterative (bottom-up) version. It uses 2*n space and is significantly faster for point updates and range queries on large inputs.
• Clarify problem requirements before coding — Ask: "Are updates point or range? Are queries point or range? What is the merge operation? Is the operation commutative?" This shapes your choice between basic segment tree, lazy segment tree, or Fenwick tree (Binary Indexed Tree).

Iterative Segment Tree (Bonus)

The iterative version uses exactly 2 * n space and operates bottom-up. It is ideal when you need maximum performance and the merge operation is commutative (like sum, min, max). Here is a compact iterative segment tree for range sum:

class IterativeSegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (2 * self.n)
        # Build leaves at positions n to 2n-1
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        # Build internal nodes bottom-up
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def update(self, pos, val):
        # Move to leaf
        i = self.n + pos
        self.tree[i] = val
        # Propagate upward
        i //= 2
        while i >= 1:
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
            i //= 2
    
    def query(self, l, r):
        # l and r are inclusive, 0-based
        l += self.n
        r += self.n
        result = 0
        while l <= r:
            if l % 2 == 1:  # l is right child — include it
                result += self.tree[l]
                l += 1
            if r % 2 == 0:  # r is left child — include it
                result += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return result

# Usage
arr = [5, 3, 7, 1, 9, 2]
ist = IterativeSegmentTree(arr)
print(ist.query(0, 5))   # 27
ist.update(2, 10)
print(ist.query(0, 5))   # 30

The iterative version shines in contests and performance-critical applications. The query loop processes l and r pointers from bottom to top, combining nodes that correspond to the queried range. This pattern works for any commutative, associative operation — just replace + with your merge function and adjust the identity element.

When to Use Segment Trees vs. Other Data Structures

Understanding the tradeoffs helps you choose the right tool during an interview:

• Fenwick Tree (Binary Indexed Tree) — Use when you only need point updates and range sum queries. It uses less memory (n+1) and is simpler. Cannot handle range min/max or range updates easily.
• Sparse Table — Use for static range minimum queries (no updates). Builds in O(n log n), queries in O(1). Cannot handle updates.
• Sqrt Decomposition (Mo's Algorithm) — Use for complex range queries that are not easily associative, or when you need to handle both range updates and queries offline.
• Segment Tree — Use when you need both updates and range queries for any associative operation, especially min/max/gcd, or when you need range updates with lazy propagation.

Conclusion

A segment tree is one of the most versatile data structures in competitive programming and technical interviews. By dividing an array into hierarchical segments, it transforms O(n) range operations into O(log n) tree traversals. The key to mastering segment trees lies in understanding the recursive divide-and-conquer pattern, practicing the three core operations (build, update, query) until they become second nature, and knowing exactly when to apply lazy propagation for range updates. Start with the recursive array-based implementation, test on small examples, and gradually move to the iterative version for efficiency. With the patterns and code templates in this guide, you will be well-equipped to handle any segment tree problem that appears in your next interview.