Back to Study Material Data Structures and Algorithms

Segment Tree

A segment tree is a data structure that allows efficient range queries and point or range updates on an array. Suppose you have an array of N integers and ...

Segment Tree

Motivation and Structure

A segment tree is a data structure that allows efficient range queries and point or range updates on an array. Suppose you have an array of N integers and you need to repeatedly answer queries like "what is the sum (or minimum, or maximum) of elements from index L to R?" A naive approach answers each query in O(N) time. A prefix sum array answers range sum queries in O(1) but cannot handle updates. A segment tree solves both problems, supporting range queries and point updates each in O(log N) time.

The segment tree is a complete binary tree built over the original array. Each leaf node represents a single element. Each internal node represents a range of elements and stores the aggregate (sum, min, max, GCD, etc.) of all elements in that range. The root node covers the entire array. A node covering range [L, R] has a left child covering [L, mid] and a right child covering [mid plus one, R] where mid equals (L plus R) divided by two.

A segment tree for an array of N elements uses at most 4N nodes when stored in an array (to handle the overhead of a complete binary tree), giving O(N) space.

Build, Query, and Update Operations

Building the segment tree takes O(N) time: recursively build left and right subtrees, then compute each internal node's value from its two children. The build function is: build(node, start, end) — if start equals end, tree[node] equals array[start]; otherwise recursively build left and right children, then tree[node] equals tree[leftChild] combined with tree[rightChild].

Range query takes O(log N) time: at each node, if its range is fully within [L, R], return the stored value; if fully outside, return the identity value (0 for sum, infinity for min); otherwise query both children and combine. Point update takes O(log N) time: update the leaf, then propagate changes up to the root by recomputing each ancestor.

Lazy propagation extends segment trees to support range updates efficiently. Instead of updating all elements in a range immediately, store a pending update at a node and propagate it to children only when those children are accessed. With lazy propagation, range updates also run in O(log N) time.

Worked Example and Interview Application

Worked example: given array [1, 3, 5, 7, 9, 11], build a segment tree for range sum queries. The root stores 36 (sum of all elements). Its left child stores 9 (sum of [1, 3, 5]) and right child stores 27 (sum of [7, 9, 11]). Query sum from index 1 to 4 (values 3, 5, 7, 9): the algorithm visits the root, splits into left [0..2] and right [3..5] ranges, and recursively collects partial sums, returning 24 in O(log 6) equals O(3) steps. After updating index 2 from 5 to 6, only the nodes on the path from leaf 2 to the root are updated — at most O(log N) nodes.

Segment trees handle non-invertible operations like GCD, maximum, and minimum that prefix arrays cannot handle with updates. They are the standard tool for competitive programming problems involving range queries with updates.

Interview tip: if a problem involves repeated range queries with intermittent updates on an array, propose a segment tree. Mention that the O(log N) per operation bound holds regardless of the query and update order, and that lazy propagation handles range updates. Contrast with a Fenwick tree (simpler, but restricted to invertible operations like sum) to show breadth of knowledge.