Coding

Segment Tree

A versatile, heap-like tree structure used for storing information about intervals or segments, allowing efficient querying of range properties and point/range updates.

Cheat Sheet

Prime Use Case

When you need to perform multiple range queries (Sum, Min, Max, GCD) on an array that is frequently updated.

Critical Tradeoffs

  • O(log N) time for both updates and queries
  • O(N) space complexity (typically 4N for array-based implementation)
  • Higher implementation overhead compared to Fenwick Trees

Killer Senior Insight

A Segment Tree is essentially a cached version of a divide-and-conquer recursion tree, where each node pre-calculates the result for a specific range to avoid redundant work.

Recognition

Common Interview Phrases

'Given an array, find the sum/min/max in range [L, R]'
'Update the value at index i'
'Perform range updates [L, R] by adding value V'
'Constraints: N and Q up to 10^5'

Common Scenarios

  • Dynamic Range Sum/Minimum/Maximum Query
  • Counting inversions in an array
  • Finding the first element greater than X in a range
  • Coordinate compression problems

Anti-patterns to Avoid

  • Using it for static range sum queries (use Prefix Sums instead)
  • Using it when only point updates and prefix sums are needed (use Fenwick Tree for simplicity)
  • Using it for 2D ranges without considering memory constraints

The Problem

The Fundamental Issue

The 'Update-Query' bottleneck: Brute force updates are O(1) but queries are O(N), or Prefix Sum queries are O(1) but updates are O(N). Segment Trees balance both at O(log N).

What breaks without it

Time Limit Exceeded (TLE) on large datasets (N, Q > 10^5)

Inefficient handling of range-based updates (O(N) per update)

Why alternatives fail

Prefix Sums are immutable; a single update invalidates the entire prefix array.

Square Root Decomposition is O(sqrt N), which might be too slow for tight 1-second limits.

Mental Model

The Intuition

Think of a corporate hierarchy: the CEO knows the total revenue of the whole company, VPs know the revenue of their departments, and managers know their teams. To find the revenue of a specific group of teams, you ask the fewest high-level managers possible instead of every single employee.

Key Mechanics

1

Recursive division of the array into two halves until leaf nodes (size 1) are reached.

2

Internal nodes store the merged result of their children.

3

Querying involves traversing only the nodes that fully or partially cover the target range.

4

Lazy Propagation: Delaying range updates by storing 'pending' values in nodes until they are actually needed.

Framework

When it's the best choice

  • When the range operation is non-invertible (like Max/Min/GCD) and updates are required.
  • When range updates (not just point updates) are required (using Lazy Propagation).

When to avoid

  • When the array is static (use Sparse Table for O(1) queries).
  • When memory is extremely tight (Segment Trees use 4x the array size).
  • When only prefix sums and point updates are needed (Fenwick Tree is faster and more space-efficient).

Fast Heuristics

If updates exist and operation is Min/Max
Segment Tree.
If updates exist and operation is Sum
Fenwick Tree (usually).
If no updates and operation is Min/Max
Sparse Table.

Tradeoffs

+

Strengths

  • Logarithmic time complexity for both updates and queries.
  • Extremely flexible: can handle almost any associative operation.
  • Supports range updates via Lazy Propagation.
−

Weaknesses

  • High constant factor in time complexity compared to Fenwick Trees.
  • Significant memory footprint (4 * N nodes).
  • Complex to implement correctly under pressure (especially Lazy Propagation).

Alternatives

Fenwick Tree (Binary Indexed Tree)
Alternative

When it wins

When only point updates and prefix/range sums are needed.

Key Difference

Lower constant factor and uses only O(N) space, but cannot easily handle Range Max/Min or complex range updates.

Sparse Table
Alternative

When it wins

When the array is static (no updates) and you need O(1) range queries.

Key Difference

Pre-computation is O(N log N), but queries are O(1) for idempotent operations like Min/Max.

Square Root Decomposition
Alternative

When it wins

When the query type is very complex or non-standard (e.g., Mo's Algorithm).

Key Difference

O(sqrt N) performance, which is slower than O(log N) but often easier to implement for weird constraints.

Execution

Must-hit talking points

  • Mention the 4N space requirement and why it's necessary for the tree structure.
  • Explain Lazy Propagation as a way to achieve O(log N) range updates.
  • Discuss the 'Associative Property' requirement for the merge function.
  • Mention the iterative (bottom-up) implementation for better performance and smaller space (2N).

Anticipate follow-ups

  • Q:'How would you handle a 2D Segment Tree?'
  • Q:'Can you implement this persistently (Persistent Segment Tree)?'
  • Q:'What if the range is very large (e.g., 0 to 10^9)?' (Answer: Dynamic Segment Tree or Coordinate Compression).

Red Flags

Allocating only 2N space for the tree array.

Why it fails: In a heap-based array representation, the indices can reach up to 4N for a tree covering N elements if N is not a power of 2.

Forgetting to push the lazy tag to children before querying or updating a node.

Why it fails: This leads to stale data being used in calculations, resulting in incorrect query results.

Incorrect base cases in the recursive query function.

Why it fails: Can lead to infinite recursion or returning values from ranges that don't overlap with the target.