Interval/区间相关的题目类型很多，从简单的区间相交，到区间更新/查询再到多维的区间。其解法也涵盖了很多不同的算法和数据结构，比如贪婪，二分，Segment Tree, Binary Indexed Tree等等。在这篇文章将对一些常见的区间类型的题目和解法进行总结。
Interval的相交、覆盖、归并
这几个是interval相关的基本问题，涉及的题目包括但不限于:
- 给一组interval的集合，求merge之后不相交的集合
- 给定一组不想交的interval，插入一个新的interval并merge，求插入之后的interval集合
- 给定一组interval，求哪些interval是被完全包含/覆盖的，等等
这些题目通常可以比较简单地解决，我们给几个例题。
相交、覆盖
相交是很基本的操作
例题：
例题：
查找被完全包含/覆盖的interval
例题：
例题：
Set Intersection Size at Least Two(这道题同时也需要查找相交的interval，另外运用了greedy的思路)
归并
通常会把输入intervals排序，这样在每次检索要merge的interval的时候会比较方便。BST, binary search, stack都是常用的数据结构和算法。
例题：
例题：
Interval集合的深度/Line Sweep
对于一个interval的集合所覆盖的所有的点，对于其中的一个点，如果有最多的interval经过它，如果这些interval的数量k，我们定义这个interval集合的深度为k。
寻找集合深度的做法Line Sweep的做法是最合适，我们只需要想象有一条线从左向右扫过这个集合，这条线和集合里interval相交数量的最大值即为深度。这个算法中我们只需要考虑每个interval的起点和终点，所以时间复杂度为O(n)。如果要sort的话，就是O(n * log n)
例题：
Greedy
贪婪在区间问题中也有很多的应用。最常见的就是用EFT(Earliest Finishing Time)来求一个interval当中最大的不相交子集。其他的例如，EDF(Earliest Deadline First)也有很多，不一一列举。
例题:
Course Schedule III(Interval with deadline, most tasks/min delay)
Range Query/区间查询
区间查询是区间问题中很重要的一个部分。区间查询，顾名思义，对于给定的区间我们需要查询这个区间的一些性质，例如和、积，最大/小值等。同时我们可能还需要支持对于单点或者区间的更新。
我们称一个range query是decomposable，当且仅当存在一个binary operation x，当我们把range Q分解成两个不相交且相邻的区间L和R时:
- query(Q) = query(L) x query(R)
举例来说：
- 对于区间和, x = +
- 对于listing, x = union
- 对于最大最小值, x = max/min
并不是所有的区间查询都是decomposable的，比如平均值，但是平均值我们可以转化成区间和的问题。
那么对于这些decomposable的区间查询问题，我们可以利用这些性质，将其分解成更小的区间从而运用不同的数据结构来加速查询/更新的速度。
我们以区间和举例，普通的区间和问题我们用presum数组即可完成，查询O(1)即可完成。但是如果我们要支持更新的话，那时间复杂度就会大大提高，需要O(n)，对于频繁更新操作这肯定是无法接受的。而且如果我们换成区间最大/小值的问题，就没有办法像区间和一样用1D的数组就可以存，我们需要2D的数组。对于这些问题，我们需要一些更general的解法。
有很多数据结构可以在区间查询/更新的时候帮到我们我们在这里一一介绍：
把区间分解成左右两个子区间，从而递归地更新/查询。查询的时间复杂度O(log n)，单点更新时间复杂度O(log n)，用lazy propagation优化之后区间更新也可以达到O(log n)。
把区间分解成长度为2的指数的基的并集，涉及一些位操作，但是代码非常简洁。多维扩展写起来比Segment Tree更方便，但是对于RMQ(Range Minimum Query)之类的查询会复杂一些。查询的时间复杂度O(log n)，单点更新时间复杂度O(log n)。
主要用于2D range query的数据结构，把平面递归地分成四份。查询时间复杂度best case O(1), worst case O(m * n)。单点更新时间复杂度O(log(m * n)
把区间分解成长度为sqrt(n)的小区间，查询的时候查这些长度为sqrt(n)的小区间和长度为1的基本区间的组合。查询的时间复杂度O(sqrt(n))，单点更新时间复杂度O(1)。
用于不需要频繁更新情况，用O(n * log n)的空间来达到最快O(1)的查询速度。思路是把区间分解成长度为1, 2, 4...2^k的子区间，查询的时候也分解成这些子区间的组合。对于不同的查询，时间复杂度也不一样，RMQ可以达到O(1)。而区间和只有O(log n)。不支持更新。
区间查询在实际题目当中的应用远比想象中的广。很多题目都可以转化为区间查询的问题。
No comments:
Post a Comment