[LeetCode]Range Module

区间查询的问题，比较直观的思路是维护一个sorted的不相交的interval的list。每一次插入的时候，我们merge所有可能的interval，保证插入后仍然是不相交的。删除的话，一组和删除区间相交的interval，除了头尾可能还残余一部分没有被覆盖的interval，剩下的都可以抹去，我们重新插入残余的interval即可。我们可以用bst来维护这个集合，key就是interval start的值;value就是end对应的值，具体对应每一个操作：

• 插入i = [start, end]：找到大于end最小的key，对应的就是紧邻i的右边的interval。之后开始向左边扫找到所有和i相交的interval并且从bst中删除。插入merge之后的interval
• 删除i = [start, end]： 找到大于end最小的key，对应的就是紧邻i的右边的interval。之后开始向左边扫找到所有和i相交的interval并且从bst中删除。注意头尾的两个interval可能有残余的部分，要重新插入进bst中
• 查询i = [start, end]：找到大于end最小的key，对应的就是紧邻i的右边的interval。其左边相邻的interval i2必定是i2.start <= end的区间。判断其是否覆盖[start, end]即可

时间复杂度，如果bst中有k个不相交的区间。查询的时间复杂度为O(log k)，插入和删除的复杂度为O(k)。代码如下：

既然是区间查询的题目，segment tree是标准的处理区间问题的数据结构。关于其介绍可以参考这篇文章。要存的东西也十分直观，对于每一个代表区间[s, e]的节点，我们只需要存[s, e]是否被完全覆盖了即可。并且这道题都是区间更新，我们用lazy propagation可以降低时间复杂度。

值得一提的是，这道题性质我们没有办法做区间的压缩，也即是把输入区间[minVal, maxVal]映射到[0, N]的区间上。所以我们只能按照题目给的[0, 1000,000,000]范围来处理。那么在实际实现的时候，会在后面的一些test case上MLE。为了处理这种情况，我们可以牺牲一点时间复杂度，在每次更新的时候，与其做lazy propagation，我们把完全包含于更新区间[s, e]的节点的所有子节点删除。当我们再需要的时候查询/更新这些子节点的时候，我们在重新根据父节点生成他们，这样虽然牺牲了一点时间，但是我们大大节省了空间。时间复杂度的话，如果用的是lazy propagation，更新和查询的时间复杂度都为O(log MaxVal)，这里MaxVal = 1000,000,000。代码如下：