线段树

线段树

给定一组区间，对于任意点 $q$，筛选出所有包含它的区间。

将每个 EI 作为叶子结点，构造一颗完全二叉树。对于每个区间，仅在最高的完全包含于它的节点保存，因此每段区间至多被保存 $O(\log n)$ 次，空间复杂度为 $O(n\log n)$。

查询时，每个节点先报告自己存储的节点，再根据 $q$ 和左右子树区间关系递归对左右子树进行查询。