Comment on Ask HN: Fast data structures for disjoint intervals?Comments−worstspotgain2yI'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.
Comments
I've built an interval treap for a similar application. Each node holds a spanning interval derived as follows:
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.