#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/segment-tree-structure

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/segment-tree-structure

Repovive

Segment Tree Structure - Segment Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

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]$

For an array of size $n$ , you need at most $4n$ 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.