题目重点：add成本、固定值域位图和空间预算需要分开说明。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练为非空半开[a,b)，允许相接但不重叠；contains给单个点。
- 排序数组基线接受可比较数值；O(1)位图版本则必须限定整数值域U。
解题路线
- 线性版查任一区间包含x为O(n)。有序版找最后start≤x，再检查x<对应end，只需一次二分。
- add在前驱/后继验证不交叠，再插入两个数组；定位O(logn)但移动O(n)，不能把整体add说成O(logn)。平衡树支持插入查询O(logn)。
- 固定整数域位图查位O(1)，空间U bits，插区间设置覆盖点位可O(length/wordSize)或按位扫描；32位域2^32bits=512MiB还未计开销。浮点或无界整数不能无代价展开。
手动走一遍
加入[1,3)、[3,7)，contains3=True由第二段覆盖；contains7=False。加入[2,4)与已有[1,3)重叠拒绝；相邻不合并仍正确，二分按start查即可。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_left,bisect_right
class Intervals:
def __init__(self):
self.starts=[];self.ends=[]
def add(self,a,b):
if a>=b:raise ValueError("nonempty half-open interval required")
i=bisect_left(self.starts,a)
if i and self.ends[i-1]>a or i<len(self.starts) and b>self.starts[i]:
raise ValueError("overlap")
self.starts.insert(i,a);self.ends.insert(i,b)
def contains(self,x):
i=bisect_right(self.starts,x)-1
return i>=0 and x<self.ends[i]
复杂度
sorted-list contains O(logn)，add O(n)，空间O(n)。bitmap查询常数但空间O(U/wordBits)，更新量依区间宽度；不用O(1)承诺掩盖预处理成本。
易错点与追问
容易失分的边界
- 只二分end而未定义端点语义可能误查。
- 用hashset展开所有整数也可期望O(1)查询，但空间按总覆盖数，不是区间数。
继续深挖
- 若允许区间重叠，合并输入还是维护计数各适合什么操作？
- IPv6域为什么不能靠全域位图，前缀Trie能提供何种查询？
