Segment Tree Range Queries, Lazy Propagation, and When...

Master segment trees for coding interviews — range sum, range min/max, lazy propagation, and the classic problems where segment trees are the right tool.

·

Segment Tree Interview Guide: Range Queries, Lazy Propagation, and When to Use Them

Segment trees appear in hard-level coding interviews at top companies when a problem requires repeated range queries and point or range updates. If you see "given an array, answer Q queries of type: what is the min/max/sum in range [l, r]?" — and there are also updates — that's a segment tree problem.

When Is a Segment Tree the Right Choice?

The brute-force for range queries is O(n) per query: scan the range. Prefix sums handle range sum in O(1) but can't handle updates efficiently. Binary indexed trees (Fenwick trees) handle point updates and prefix queries in O(log n) but are harder to generalize.

Segment trees handle:

Use a segment tree when: queries are arbitrary ranges (not just prefixes), updates occur interleaved with queries, and n is large enough that O(n) per query is too slow.

Structure

A segment tree over an array of size n is a binary tree where each node stores information about a range. The root covers [0, n-1]. Each internal node covering [l, r] has two children covering [l, mid] and [mid+1, r]. Leaf nodes cover single elements.

The tree has O(n) nodes and fits in an array of size 4n. Node at index i has children at 2i and 2i+1 (1-indexed).

Building the Tree

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2*node, start, mid)
            self._build(arr, 2*node+1, mid+1, end)
            self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

Build time: O(n). Each node is visited once.

Range Query

def query(self, node, start, end, l, r):
    if r < start or end < l:      # No overlap
        return 0
    if l <= start and end <= r:   # Total overlap
        return self.tree[node]
    mid = (start + end) // 2
    left = self.query(2*node, start, mid, l, r)
    right = self.query(2*node+1, mid+1, end, l, r)
    return left + right

The three cases: no overlap (return identity), total overlap (return stored value), partial overlap (recurse). For sum, identity is 0. For min, identity is infinity. For max, identity is -infinity.

Point Update

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

Lazy Propagation

Point updates are O(log n), but range updates — "add 5 to all elements in [l, r]" — require updating every element, which is O(n log n). Lazy propagation defers these updates: mark a node as "pending update" and apply it only when the node is visited.

Add a lazy array alongside tree. When doing a range update on [l, r]:

def push_down(self, node):
    if self.lazy[node] != 0:
        self.tree[2*node] += self.lazy[node] * (mid - start + 1)
        self.tree[2*node+1] += self.lazy[node] * (end - mid)
        self.lazy[2*node] += self.lazy[node]
        self.lazy[2*node+1] += self.lazy[node]
        self.lazy[node] = 0

This reduces range update + range query to O(log n) each.

Classic Problems

Range sum with updates: The canonical segment tree problem. Build, support point updates and range sum queries.

Range minimum query (RMQ): Replace the merge operation with min. Can also use sparse table for static arrays (O(1) query, O(n log n) build, no updates).

Count of elements in range with condition: Augment nodes to store counts or sorted arrays. With a merge sort tree (segment tree of sorted arrays), you can count elements ≤ k in [l, r] in O(log² n).

Interval coloring: Track max and min colors in a range with lazy propagation for range-set operations.

Interview Approach

Segment tree problems on LeetCode are typically hard-tagged. Recognize them by: "array + range queries + updates." In an interview, the approach is:

  1. State the brute force and its complexity
  2. Identify that prefix sums or binary search won't work due to updates
  3. Propose segment tree: O(n) build, O(log n) query and update
  4. Code the build and query first; add lazy propagation only if range updates are needed

If the interviewer asks about alternatives: sparse table for static range queries (O(1) query), Fenwick tree for prefix sum problems (simpler code, similar complexity), sqrt decomposition for simpler implementation with O(√n) per operation.

What Interviewers Want to See

Interviewers asking segment tree problems at FAANG are testing whether you can handle complex recursive tree structures under time pressure. They want to see: correct boundary handling (0-indexed vs 1-indexed, inclusive bounds), understanding of the three-case query logic, and the ability to generalize the merge operation.

Practice LeetCode 307 (Range Sum Query - Mutable), 315 (Count of Smaller Numbers), and 699 (Falling Squares) to get fluent with the pattern.

Ready to practice for your next interview? Interview Simulator gives you AI-powered feedback on your responses — behavioral, technical, and system design. Start with 3 free practice interviews today.

Try Interview Simulator free →

Strong fundamentals in data structures and algorithms are the foundation of technical interviews.

Continue building your skills with Mastering Behavioral Interviews: STAR Method + 25 Sample....

Continue building your skills with Cracking the System Design Interview: A Framework That....

Recognizing coding interview patterns is more effective than memorizing individual solutions.

Keep our data structures cheat sheet handy during practice sessions.

Explore Related Topics

Related Reading