Range Module Solution

The trickiest part is handling partial overlaps during add and remove. For addRange:

$1.$ Find all intervals overlapping $[\text{left}, \text{right}]$

$2.$ Compute the union (extend left and right as needed)

$3.$ Remove old intervals, insert the union For removeRange:

$1.$ Find all intervals overlapping $[\text{left}, \text{right}]$

$2.$ For each, trim or split as needed

$3.$ Update the map

Time per operation: $O(\log n + k)$ where $k$ is affected intervals. Amortized $O(\log n)$ since each interval is added/removed once. Time: $O(n)$. Space: $O(n)$.