Course contentsShow
← Computer Science
Lesson 643 of 2,87215. Tries and Specialized TreesFree lesson

Building a Segment Tree

Constructing a segment tree from an input array using recursive divide-and-conquer, computing aggregate values bottom-up.

Building a Segment Tree

You'll learn: How to construct a segment tree from an array by recursively dividing the range and computing aggregate values from the leaves upward.

The Core Construction Process

Building a segment tree means transforming a flat array into a tree where each node stores summary information (like sum, min, or max) about a contiguous range of elements. You do this using divide-and-conquer: split the array in half repeatedly until you reach single elements, then combine results on the way back up.

Think of it like organizing a tournament bracket. Each match (node) combines results from two smaller matches (child nodes), and the leaves represent individual players (array elements).

The Recursive Build Algorithm

Starting at the root, you:

  1. Base case: If the range contains just one element, create a leaf node storing that element's value
  2. Recursive case:
    • Find the midpoint of the current range
    • Recursively build the left subtree for the left half
    • Recursively build the right subtree for the right half
    • Compute the current node's value by combining (merging) the two children's values

For example, if building a "range sum" tree from [3, 1, 4, 2]:

  • Leaves store 3, 1, 4, 2
  • Their parents store 3+1=4 and 4+2=6
  • The root stores 4+6=10

The construction happens bottom-up even though the code is written recursively—you must know the children's values before computing the parent's.

Time and Space

Building takes O(n) time because you visit each of the ~2n tree nodes once. You need O(n) space for the tree array.

Key Takeaway: Building a segment tree uses recursive divide-and-conquer to split the input range into halves, creating leaves for single elements, then computing each parent's aggregate value by combining its children's values bottom-up.