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
4nto be safe) - Node at index
ihas:- Left child at index
2*i - Right child at index
2*i + 1 - Parent at index
i/2
- Left child at index
- Root is at index
1(index0often 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.