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

Segment Tree Structure and Representation

Building the tree structure that divides arrays into segments, using array-based representation with parent-child relationships.

Segment Tree Structure and Representation

You'll learn how segment trees organize array data into a hierarchical tree structure using parent-child relationships in array form.

The Core Idea

A segment tree divides an array into overlapping segments and stores them in a binary tree structure. Each node represents a range (segment) of the original array. The leaf nodes represent individual elements, while internal nodes represent merged information from their children's ranges.

Think of it like organizing a school: the principal oversees all students (root = entire array), vice-principals manage different grade levels (internal nodes = sub-ranges), and individual teachers handle specific classes (leaves = single elements). Each level has responsibility for a portion of the whole.

Tree Structure

The segment tree is a complete binary tree where:

  • The root represents the entire array [0...n-1]
  • Each internal node's left child covers the first half of its range
  • Each internal node's right child covers the second half
  • Leaf nodes represent single array elements

For an array of size n, the tree has height approximately log₂(n).

Array-Based Representation

Just like binary heaps, segment trees use array representation with index relationships:

  • Store the tree in a 1D array (typically size 4n to be safe)
  • Node at index i has:
    • Left child at index 2*i
    • Right child at index 2*i + 1
    • Parent at index i/2
  • Root is at index 1 (index 0 often unused)

Each node stores both its range boundaries [left, right] and computed aggregate data (sum, min, max, etc.) for that segment.

Key Takeaway: Segment trees use a complete binary tree structure dividing arrays into nested segments, efficiently represented as an array where parent-child relationships follow the 2*i and 2*i+1 indexing pattern, enabling range queries without complex pointer management.