I've built an interval treap for a similar application. Each node holds a spanning interval derived as follows:

   node->spanning = union(node->interval, node->left->spanning, node->right->spanning) 

On rotations, only two spanning intervals need to be recomputed. You can search for an interval and the result is the subset of nodes whose intervals overlap with it. And of course, rotations keep the treap balanced at all times.