Segment Tree

Definition

A Segment Tree is a binary tree used for storing information about intervals or segments. It allows you to query a range (like “what is the sum of elements from index 2 to 6?”) and update elements very efficiently.

How it Works

1. Structure: The leaves of the tree are the original array elements.
2. Internal Nodes: Each internal node stores a summary (sum, min, or max) of its children.
3. Root: The root node stores the summary of the entire array.

Real-World Analogy:

Think of a Sports Tournament Bracket.

• The bottom row contains individual match scores.
• The next row up sums the scores of pairs.
• The top (root) holds the total score of the entire tournament.
  If one match score changes, you only need to update the specific path up to the root, not the whole bracket.

Example

Array: [1, 2, 5, 10] (Size 4)

Tree:

• Leaves: 1, 2, 5, 10
• Mid-level: 3 (1+2) and 15 (5+10)
• Root: 18 (3+15)
  Query Sum(0, 3): Returns Root (18).

Complexity Analysis

• Time Complexity:

• Build: O(n)
• Query: O(log n)
• Update: O(log n)

• Space Complexity: $O(4n)$ (Requires extra memory for the tree structure).

Use Cases

• Range Sum Query: Quickly calculating sums in a subarray.
• Range Min/Max Query: Finding the smallest/largest number in a range.
• Computational Geometry: Solving problems involving overlapping rectangles.