Segment Tree for Intervals

Sometimes interval queries map to segment tree operations.

Given $n$ intervals on a range $[0, M]$, answer queries like:

• "How many intervals cover point $x$?"
• "What's the maximum overlap in range $[l, r]$?"

Build a segment tree on positions $0$ to $M$.

For each interval $[l, r]$, do a range update: add 1 to all positions from $l$ to $r$. To count intervals covering point $x$: point query at $x$.

This approach works when $M$ is small enough. For large $M$, use coordinate compression.