Data Structures
Segment Tree
Difficulty: Advanced
Given an array and a stream of mixed queries (sum(L, R), min(L, R), plus single-index updates), prefix sums answer the queries in O(1) but pay O(n) for every update, while a raw array does the opposite. Neither extreme is acceptable when...
Segment Tree
Given an array and a stream of mixed queries (sum(L, R), min(L, R), plus single-index updates), prefix sums answer the queries in O(1) but pay O(n) for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A Segment Tree balances the two: every operation runs in O(log n) after an O(n) build.
This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the 4n flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in O(log n), and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate.
In Arrays & Strings, a flat array gave you O(1) indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. Trees: Binary Tree Fundamentals is where the recursive shape and the O(h)-stack traversal pattern came from, and you reuse both directly here.
Next, Fenwick Tree (BIT) solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the range query problem and why segment trees provide an optimal balance between query and update performance.
Build a segment tree from an array using recursive construction in O(n) time.
Implement point update and range query operations in O(log n) time.
Implement lazy propagation for efficient O(log n) range updates.
Analyze time and space complexity of all segment tree operations.
Apply segment trees to solve range sum, range minimum, and range maximum query problems.
Why This Matters
01
Segment trees solve the fundamental range query problem: answering questions like 'what is the sum/min/max of elements from index L to R?' in O(log n) time while supporting O(log n) updates. Without a segment tree, you must choose between O(1) queries with O(n) updates (prefix sums) or O(n) queries with O(1) updates (raw array).
02
Lazy propagation extends segment trees to handle range updates in O(log n) rather than updating each element individually. This technique of deferring computation until needed appears throughout computer science, from virtual memory to database query optimization.
03
Segment trees appear in hundreds of competitive programming problems and are a standard tool in advanced technical interviews. Understanding them signals fluency with divide-and-conquer on intervals, recursive tree construction, and efficient data structure design.
04
The concepts behind segment trees -- hierarchical aggregation, interval decomposition, and lazy evaluation -- generalize to advanced structures like Fenwick trees, merge sort trees, persistent segment trees, and 2D segment trees.
Key Terms
7 terms you'll encounter in this lesson
Segment Tree
A binary tree data structure where each node stores the aggregate (sum, min, max, etc.) of a segment (contiguous subarray) of the original array. Leaf nodes represent individual elements; internal nodes represent merged results of their children.
Range Query
A query that asks for an aggregate value (sum, minimum, maximum, etc.) over a contiguous subrange [L, R] of an array.
Point Update
An operation that changes a single element in the underlying array and propagates the change up through all ancestor nodes in the segment tree, maintaining correctness in O(log n) time.
Lazy Propagation
An optimization technique where pending range updates are stored in internal nodes and only pushed down to children when those children are actually accessed. This defers work and enables O(log n) range updates.
Lazy Tag
A value stored at a segment tree node indicating a pending update that has not yet been applied to its children. When the node is next accessed, the tag is pushed down (propagated) to both children.
Push Down
The operation of propagating a lazy tag from a parent node to its two children, applying the deferred update before proceeding with a query or further update on the children.
Node Indexing (1-based)
In array-based segment trees, the root is at index 1. For a node at index i, its left child is at 2i and its right child is at 2i+1. The parent of node i is at floor(i/2).
Heads Up
Common misconceptions to watch out for
"A segment tree requires O(2n) space because it is a binary tree with n leaves"
A segment tree needs O(4n) space in the worst case, not 2n. The tree may not be a perfect binary tree when n is not a power of 2, so some internal nodes at the deepest level are unused. Allocating 4n entries guarantees enough space for any n.
"Prefix sums are always better than segment trees for range sum queries"
Prefix sums give O(1) range queries but O(n) for updates (must rebuild the prefix array). Segment trees give O(log n) for both queries and updates. When the array is static (no updates), prefix sums are better. When updates are needed, segment trees win.
"Lazy propagation means updates are never actually applied"
Lazy propagation defers updates, but they are always applied before their results are needed. The push-down step ensures that when you query or update a child, any pending lazy tags from ancestors are applied first. Correctness is maintained; only unnecessary work is avoided.
"You can use a segment tree only for sum queries"
Segment trees work for any associative operation that can merge two interval results: sum, min, max, GCD, bitwise OR/AND, count, and more. The merge function at each internal node determines the type of query.