Segment Trees

# CHAPTER 17

Segment Trees #

1. Introduction #

1. 1. "What is the total sum of transactions between Index 50,000 and Index 900,000?"

1. 2. "Transaction at Index 150,000 was a typo, update it to $50."

If you use a standard Array for loop to calculate the sum, it takes $O(N)$ Time. Doing that thousands of times will freeze the server. If you pre-calculate all sums, updating a single index requires recalculating everything ($O(N)$). We need a data structure that can calculate massive Range Queries AND handle Dynamic Updates at blistering speeds. Enter the Segment Tree. By caching mathematical intervals geometrically inside a tree, we crush both operations down to exactly $O(\log N)$ Time.

2. Learning Objectives #

• Understand the hierarchical interval-caching architecture of a Segment Tree.

• Execute the $O(N)$ algorithm to construct the tree from a baseline array.

• Perform $O(\log N)$ Range Queries (Sum, Min, Max).

• Perform $O(\log N)$ Point Updates dynamically.

3. The Architecture (Caching Intervals) #

• The Leaf Nodes are the exact, individual numbers from your base array.

• The Internal Nodes store the "Merged Answer" (e.g., the Sum) of their two underlying Left and Right children.

• The Global Root stores the ultimate answer for the entire array (Index 0 to $N-1$).

Visual Example (Sum Segment Tree): Array: [1, 3, 5, 7]

           [Sum: 16] (Indices 0-3)
           /       \
      [Sum: 4]    [Sum: 12]
      (Idx 0-1)   (Idx 2-3)
       /   \       /    \
     [1]   [3]   [5]    [7]
   (Idx 0)(Idx 1)(Idx 2)(Idx 3)

*(Notice how the geometry works: Node 4 is the sum of leaves 1 and 3. The Root 16 is the sum of children 4 and 12).*

4. Answering Range Queries ($O(\log N)$) #

The Query Overlap Rules:

1. 1. Total Overlap: The Node's interval is completely inside the query range. Return the Node's cached value instantly!

1. 2. No Overlap: The Node's interval is completely outside the query range. Return $0$ (for Sum) or Infinity (for Min).

1. 3. Partial Overlap: The Node is partially inside. Branch recursively Left AND Right and merge the answers.

5. Executing Point Updates ($O(\log N)$) #

1. 1. Start at the Root. Recurse downwards toward Index 2.

1. 2. Update the Leaf [5] to [9].

1. 3. As the recursion unwinds (backtracks), dynamically recalculate the parent.

1. 4. The Parent (Idx 2-3) was 5+7=12. It updates to 9+7=16.

1. 5. The Root (Idx 0-3) updates to 4+16=20.

6. Array Implementation #

7. Complexity Analysis #

• Time Complexity (Tree Build): $O(N)$ (Executed once during startup).

• Time Complexity (Query/Update): $O(\log N)$ (The ultimate optimization).

• Space Complexity: $O(N)$ (Specifically requiring a $4N$ sized array matrix).

8. Common Mistakes #

• Applying Segment Trees to Static Data: If the database *never* updates, building a Segment Tree is a waste of memory. You should just build a standard "Prefix Sum Array" which handles static range queries in $O(1)$ time. Segment Trees are explicitly designed for environments with chaotic, constant dynamic updates!

9. Exercises #

1. 1. Draw a Minimum (Min) Segment tree for the array [8, 2, 5, 1, 9]. The parent nodes should store the minimum of their two children.

1. 2. Trace the exact nodes updated in the visual tree (from Section 3) if Array Index 3 changes from 7 to 10.

10. MCQs with Answers #

11. Interview Preparation #

• *Advanced Scaling Strategy:* "You have an array of 100,000 items. An algorithm makes 50,000 updates, and 50,000 range queries randomly. Will you use a raw Array, a Prefix Array, or a Segment Tree?" *(Answer: A Segment Tree! A raw Array handles updates fast $O(1)$, but queries slow $O(N)$. A Prefix Array handles queries fast $O(1)$, but updates slow $O(N)$. The Segment Tree flawlessly handles BOTH operations in optimized $O(\log n)$ balance!)*

12. Summary #

13. Next Chapter Recommendation #