线段集合求交问题：每次添加线段后如何以O(log|M|+log|N|)复杂度计算总交点数

该实现基于两个通用前提：1. 仅统计M与N两个集合之间的线段交点，不计算同一集合内部的线段交点；2. 默认M为水平线段集合、N为垂直线段集合（如果两个集合都允许混存水平、垂直两种线段，只需要拆分存储两个方向的子集合即可，复杂度量级不变）。如果要处理任意方向的线段，无法达到要求的时间复杂度。

核心思路 #

不用每次添加完线段重新统计所有交点，全局维护一个总交点计数器total，初始值为0。新增线段只会和对面集合的原有线段产生新的交点，之前的交点已经统计过不需要重复计算，每次添加完把新增交点数累加到total里直接输出就行。

具体实现 #

数据结构准备 #

• 水平线段统一存为三元组(y坐标, x左端点, x右端点)，用一个按y值升序排序的平衡二叉搜索树（比如C++的std::set、Python的sortedcontainers.SortedList）存储，搭配一个支持范围查询、单点更新的树状数组/线段树存x区间的标记
• 垂直线段统一存为三元组(x坐标, y下端点, y上端点)，用一个按x值升序排序的平衡二叉搜索树存储，搭配一个支持范围查询、单点更新的树状数组/线段树存y区间的标记

添加操作逻辑 #

往M里加水平线段

1. 先查对面N里有多少条垂直线段满足两个条件：x在当前水平线段的左右端点之间，且水平线段的y值在垂直线段的y上下限之间，这个查询的时间复杂度是O(log|N|)
2. 把查到的数量加到total里
3. 把新的水平线段插入M的存储结构中，插入时间复杂度O(log|M|)
4. 输出当前的total值

往N里加垂直线段

1. 先查对面M里有多少条水平线段满足两个条件：y在当前垂直线段的上下端点之间，且垂直线段的x值在水平线段的x左右限之间，查询时间复杂度O(log|M|)
2. 把查到的数量加到total里
3. 把新的垂直线段插入N的存储结构中，插入时间复杂度O(log|N|)
4. 输出当前的total值

边界处理 #

如果遇到线段端点重合、三线共点的情况，只需要调整查询条件的区间开闭（比如把小于改成小于等于）即可，不会额外增加时间复杂度。如果坐标范围过大，提前做坐标离散化或者用动态开点的线段树就能避免空间浪费。

内容的提问来源于stack exchange，提问作者AshGi