For #1 a Discrete Interval Encoding Tree may be what you want.

https://web.engr.oregonstate.edu/~erwig/diet