Sorted unsigned integer intervals tree structure
Interval trees seem like a natural candidate. The Wikipedia page has links to implementations in various languages. 
You can overwrite an existing interval by querying its endpoints, then removing the resulting intervals on the left and right, and then adding back the truncated intervals together with the new one.