Segment Tree

Segment Tree

🌳 What Segment Tree Can Solve (Use-Cases)

Segment Trees are best when:

• You have a static array (size doesn’t change)

• You need to answer range queries (like sum, min, max, gcd, etc.)

• And you also need to update individual elements efficiently

💡 Categories of Problems Segment Trees Solve:

1. Range Queries + Point Updates

You want to:

• Query info in range [l, r]

• Update value at index i

✅ Examples:

• Range sum

• Range min/max

• Range gcd/lcm

• Range xor

2. Range Queries + Range Updates

You want to:

• Query info in [l, r]

• But also update entire ranges, like add 5 to all elements in [l, r]

✅ Examples:

• Add to a subarray

• Set all elements in [l, r] to X

• Lazy propagation is used here

3. Counting / Frequency Queries

For example:

• Count how many times k appears in [l, r]

• Count number of elements > X in [l, r]

✅ Segment Tree can store frequency tables in each node

4. Kth Order Statistics in Range

Like:

• Find the kth smallest/largest element in [l, r]

✅ Segment Tree with sorted vectors or Merge Sort Tree is used

5. Range Search

For example:

• Find the first index in [l, r] where value ≥ x

• Find the maximum prefix or suffix with certain property

6. Dynamic Programming Optimization

Often used in:

• Range DP problems

• Tree DP

• Problems like: "choose subarrays such that..."

✅ Segment Tree helps answer DP states efficiently

7. 2D Problems (Advanced)

2D Segment Trees handle range queries in 2D space (like a matrix)

8. Segment Tree Beats / Advanced Use-Cases

Even handles:

• Max subarray sum with updates

• Conditional range updates

• Convex hull trick style queries

(These are competitive level pro topics)

🧠 Example Problems per Category: