Segment Tree Animation Tutorial - Interactive Learning
Master Segment Tree - DSA Learning Platform 📊 Master Segment Tree Range Queries O(log n) Operations Learn segment tree operations with interactive animations and range query visualization 📖 Understanding Segment Tree Introduction Structure Build Tree Range Query Point Update Applications What is a Segment Tree? A Segment Tree is a binary tree data structure used for storing information about intervals or segments. It allows querying which segments contain a given point, or performing aggregate queries (sum, min, max) over a range. The key advantage is that it can answer range queries and point updates in O(log n) time, compared to O(n) for naive approaches. Problem It Solves Query: sum(arr[L...R]) in O(log n) Each node in the segment tree represents a range of the array and stores aggregated information (like sum, min, or max) for that range. 🔑 Key Characteristics Binary tree structure Each node represents a range [L, R] Leaf nodes = individual array elements Internal nodes = aggregate of children Range query in O(log n) Point update in O(log n) Space complexity: O(4n) ≈ O(n) Segment Tree Structure For an array of size n, the segment tree: Root: Represents entire array [0, n-1] Left child of node [L,R]: [L, mid] Right child of node [L,R]: [mid+1, R] Leaves: Single elements [i, i] Tree Size Size = 4 × n (safe upper bound) Child Indices (1-indexed) Left = 2×i, Right = 2×i+1 The tree is typically stored in an array where index 1 is the root, and for any node at index i, its children are at 2i and 2i+1. 📍 Segment Tree for Array [1, 3, 5, 7, 9, 11] [36] [0-5] / \ [9] [27] [0-2] [3-5] / \ / \ [4] [5] [16] [11] [0-1] [2] [3-4] [5] / \ / \ [1] [3] [7] [9] [0] [1] [3] [4] Leaf nodes = Array elements Internal nodes = Sum of children Building the Segment Tree The tree is built recursively using divide and conquer: Build Algorithm If range has single element (leaf), store array value Otherwise, find mid = (L + R) / 2 Recursively build left subtree for [L, mid] Recursively build right subtree for [mid+1, R] Store aggregate (sum/min/max) of children Build Time Complexity O(n) - visits each element once 📝 Build Process Start with full range [0, n-1] Divide into halves recursively Base case: single element range Merge results going up 💡 Merge Operations Sum: left + right Min: min(left, right) Max: max(left, right) GCD: gcd(left, right) Range Query Operation To query a range [qL, qR], we traverse the tree and combine results: Query Algorithm No overlap: Node range outside query → return identity Total overlap: Node range inside query → return node value Partial overlap: Query both children and merge No Overlap Return 0 (sum) or ∞ (min) Total Overlap Return node value Partial Overlap Recurse both sides ⏱️ Query Complexity Time: O(log n) Space: O(log n) stack 🔍 Query Example Query sum([1, 4]) on array [1,3,5,7,9,11] Nodes [1-2] and [3-4] have total overlap Return: 3+5+7+9 = 24 Point Update Operation To update element at index i with new value: Update Algorit...
Subject: Data Structures with Animation | Chapter: Segment Tree Data Structure