What is a Segment Tree?

Learn what a segment tree is, how range queries and lazy propagation work, and how to answer this interview question well.

hardQ62 of 227 in Data Structures & Algorithms Est. time: 6 minsLast updated: July 2026

Open Code Lab

Expected Interview Answer

A segment tree is a binary tree built over an array that stores a precomputed aggregate (sum, min, max, or similar) for every contiguous sub-range at each node, letting range queries and point or range updates both run in O(log n) time instead of O(n).

The tree is typically stored implicitly in an array where each internal node represents the aggregate of a range, its left child covers the first half of that range and its right child covers the second half, recursively down to leaves that represent single elements. Building the tree takes O(n) time since there are 2n-1 nodes total. A range query decomposes the requested range into at most O(log n) pre-aggregated node ranges that exactly cover it, combining their stored values without touching individual elements. A point update walks from the corresponding leaf up to the root, recomputing O(log n) ancestor aggregates along the way; range updates use an additional technique called lazy propagation to defer pushing updates down until a query actually needs that subtree, keeping range updates O(log n) as well instead of O(n). Segment trees are the standard tool for range-sum, range-minimum, or range-maximum queries with frequent updates, beating a plain prefix-sum array whenever updates are common.

O(log n) range query and O(log n) update, both directions
Handles range-sum, range-min, range-max, and custom aggregates
O(n) build time with 2n-1 total nodes
Lazy propagation extends it to O(log n) range updates

AI Mentor Explanation

A segment tree is like a scoring ledger that keeps a running total not just per over but for every larger grouping of overs, all the way up to the full innings. Instead of adding up every single ball to answer "what was the total in overs 12 through 27", the ledger already has precomputed totals for chunks like overs 12-19 and 20-27 sitting ready, so it just combines a handful of chunk totals. When one ball's result is corrected after review, only the chunks containing that ball need their totals refreshed, walking up from the smallest chunk to the full innings total, not the whole ledger. This precomputed, hierarchical chunking is what turns a slow ball-by-ball recount into a quick handful of lookups.

Step-by-Step Explanation

Step 1
Build recursively
Each node covers a range; leaves hold single elements; internal nodes store the aggregate of their two children’s ranges, built in O(n).
Step 2
Query by decomposition
Split the requested range into at most O(log n) node ranges that exactly cover it, then combine their stored aggregates.
Step 3
Point update
Update the corresponding leaf, then walk up recomputing each ancestor’s aggregate, O(log n) total.
Step 4
Range update with lazy propagation
Defer pushing an update into child nodes until a query actually needs that subtree, keeping range updates O(log n).

What Interviewer Expects

Explain how range queries decompose into O(log n) pre-aggregated nodes
State both O(log n) query and O(log n) update time complexities
Describe lazy propagation and why it is needed for efficient range updates
Compare against a plain prefix-sum array and when each is preferable

Common Mistakes

Confusing a segment tree with a Fenwick tree (binary indexed tree), which is more limited but simpler
Forgetting lazy propagation, causing range updates to degrade to O(n)
Not recomputing ancestor aggregates all the way to the root after a point update
Assuming a prefix-sum array is always sufficient, ignoring frequent-update workloads

Best Answer (HR Friendly)

“A segment tree precomputes answers for chunks of a range so I can answer any "what's the total (or min/max) between these two positions" question by combining a handful of precomputed chunks instead of scanning everything. It also lets me update a value and only refresh the small number of chunks that contain it, so both queries and updates stay fast even on huge datasets.”

Code Example

Segment tree for range-sum query and point update

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        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, value):
        i = pos + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        # sum over [left, right)
        result = 0
        left += self.n
        right += self.n
        while left < right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                result += self.tree[right]
            left //= 2
            right //= 2
        return result

seg = SegmentTree([1, 3, 5, 7, 9, 11])
print(seg.query(1, 4))  # sum of indices 1..3 => 15
seg.update(1, 10)
print(seg.query(1, 4))  # updated sum => 22

Follow-up Questions

How does a segment tree compare to a Fenwick tree (binary indexed tree)?
How does lazy propagation keep range updates at O(log n)?
How would you adapt a segment tree for range-minimum queries instead of range-sum?
How would you build a persistent segment tree to query past versions of the array?

MCQ Practice

1. What is the time complexity of a range query on a segment tree?

2. What technique allows range updates to also run in O(log n) instead of O(n)?

3. How many total nodes does a segment tree over n elements typically have?

Flash Cards

1 / 4

What is a Segment Tree?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Build recursively

Query by decomposition

Point update

Range update with lazy propagation