Segment Tree (Conceptual)

A segment tree is a binary tree built over an array to support efficient range queries and point updates.

Typical operations:

  • Query aggregate over a range [L, R] (sum, min, max, etc.).
  • Update a single element a[i] (or sometimes a range).

Both can be done in O(log n) time, making segment trees ideal for scenarios with many interleaved queries and updates.

High-Level Idea

Given an array a[0..n-1], a segment tree:

  • Builds a tree where each node represents a segment (interval) of the array.
  • The root represents [0, n-1].
  • Each node’s children represent left and right halves of its segment.

Each node stores an aggregate for its segment:

  • For sum queries: the sum of elements in that segment.
  • For min queries: the minimum value in that segment.
  • etc.

Querying a Range

To query [L, R]:

  1. Start at the root segment [0, n-1].
  2. Recursively visit child segments:
    • If a segment is completely outside [L, R], ignore it.
    • If a segment is completely inside [L, R], use its stored aggregate directly.
    • If a segment partially overlaps, split further.

Because each level of the tree halves the segment size, there are only O(log n) segments that contribute to any given range query.

Updating a Point

To update a[i] to a new value:

  1. Find the leaf node corresponding to index i.
  2. Update the leaf’s value.
  3. Recompute aggregates on the path from that leaf back up to the root.

This touches O(log n) nodes.

When Segment Trees Are Useful

Segment trees are a good fit when:

  • You have many range queries (sum/min/max) and point updates.
  • A simple prefix sum array is insufficient because updates are too frequent.

Examples:

  • Online range sum queries with updates.
  • Range minimum/maximum queries with updates.
  • More advanced uses: range add + range query (with lazy propagation).

Trade-offs

Pros:

  • O(log n) per query and per update.
  • Flexible: can support many types of associative operations (sum, min, max, gcd, etc.).

Cons:

  • Higher constant factors and memory usage (O(4n) typical).
  • Implementation is more complex than Fenwick trees for some operations.

In interviews, you are more likely to explain the concept and maybe sketch simpler variants; full lazy propagation is more common in competitive programming.