Data Structures19 sections · 729 units
Open in Course

Segment Tree Structure

Divide and conquer on arrays

A segment tree is a binary tree where:

  • Each leaf represents a single array element
  • Each internal node represents a range and stores aggregate info (sum, min, max, etc.)
  • The root represents the entire array [0,n−1][0, n-1]

For an array of size nn, you need at most 4n4n nodes (to handle non-power-of-2 sizes safely).

Array: [2, 1, 5, 3, 4]

Segment tree (sum):
           [15]          (0-4)
          /    \
       [8]      [7]      (0-2), (3-4)
       / \      / \
     [3] [5]  [3] [4]    (0-1), (2), (3), (4)
     / \
   [2] [1]               (0), (1)

Each node stores the sum of its range. The root stores the total sum.