一维有序数组中，落在半开区间[a,b)里的键占据连续位置，两次二分就能求个数。二维点按x排序以后，一个矩形的x范围仍然连续，但其中满足y范围的点可能交错出现。把一个维度排好，没有同时解决另一个维度。

本篇先处理所有矩形查询预先给定的离线问题。扫描x时用11篇Fenwick树维护y计数，把二维条件拆成一次排序和一维动态前缀和。随后比较范围树与空间分解，说明它们为在线查询保存了哪些额外信息。

半开矩形与重复点

输入为n个整数点和q个矩形。矩形用(xlo,ylo,xhi,yhi)表示，计入满足xlo≤x<xhi且ylo≤y<yhi的点。左右或上下界倒置抛出ValueError；零宽、零高矩形返回0。重复坐标按输入中的独立点计数，空点集合法。

输出按矩形输入顺序返回计数。这里不返回点的身份列表：计数结果只有q个整数，报告查询则可能输出总计z个点引用，必须增加至少Ω(z)的写出成本。坐标比较、索引和计数加减按字长足够的RAM单位成本计算；Python大整数另有位长成本。

离线表示整个点集和查询集合在运行前已知。可以重排查询执行顺序，再用查询ID放回答案；不能据此声称同一接口支持未知下一条查询的在线流，也没有动态点插入删除接口。

用四个严格前缀表达一个矩形

定义F(X,Y)为满足x<X且y<Y的点数。容斥给出

C=F(xhi,yhi)−F(xlo,yhi)−F(xhi,ylo)+F(xlo,ylo).C=F(xhi,yhi)-F(xlo,yhi)-F(xhi,ylo)+F(xlo,ylo).

对任意一个点，把它对四项的贡献相加，结果恰好是两个半开区间指示函数的乘积。区间内贡献1，区间外贡献0，所以对所有点求和得到正确计数。这个逐点证明同样适用于重复点，无须先去重。

实现可以合并成两个x事件：在xhi处加上当前y区间计数，在xlo处减去同一区间计数。每个事件只查询一次Fenwick的半开区间和。

把点按x排序，事件也按X排序。处理阈值X前，指针持续插入所有x<X的点；x=X的点留给后面更大的阈值。于是处理事件时，Fenwick恰好包含严格x前缀中的点。这个不变量把二维问题缩成y区间计数。

坐标压缩保留次序，不保留距离

将输入点的不同y值排序成数组ys。点的y映射为其在ys中的下标，重复点对同一下标重复加1。查询边界不一定出现在点集中：用bisect_left(ys,Y)取得严格小于Y的坐标个数。

因此y区间对应[bisect_left(ys,ylo), bisect_left(ys,yhi))，可直接调用11篇的Fenwick.sum(left,right)。输入为空时ys为空，合法前缀和仍为0。

压缩只保持比较次序。例如坐标1与1000000可能映射到相邻下标，不能把下标差当欧氏距离。正交范围计数只需要次序，所以这种压缩足够；最近邻距离或面积计算不能不加说明地使用压缩下标。

若点为(2,3)，矩形为[0,2)×[0,4)，答案应为0。把扫描条件写成x≤X，就会在右边界计入这个点。若把y的bisect_left改成bisect_right，也会在上边界引入同类错误。边界语义不是最后统一“减一”就能修正的实现细节，特别是负坐标和稀疏坐标没有共同的步长。

成本来自排序、插入与查询

点排序和坐标压缩共O(n log(n+1))，2q个事件排序O(q log(q+1))。每个点只插入一次Fenwick，每个事件查询一次，分别是O(log(n+1))。

总时间可合写为最坏O((n+q) log(n+q+1))，额外空间O(n+q)。这不依赖随机输入，也没有期望或高概率假设。Fenwick单次操作本身有最坏对数界，扫描指针总共前进n次；不应把这两种计费解释为未经说明的平均情况。

当q=1且不需要后续查询时，直接扫描n个点更简单，也只需O(n)时间。离线结构的价值在于同一批大量查询共享排序和更新，而不是对任何输入都优于朴素扫描。

在线查询要保留二维信息

静态二维范围树先按x建立平衡树，每个节点再保存其子树点按y排序的关联表。一个x区间分成O(log n)个互不重叠的标准子树；在各自的y表中二分，可计数或报告符合条件的点。

每个点沿主树的O(log n)层出现在关联表中，所以空间O(n log n)。普通版本每个标准子树花O(log n)查询，计数最坏O(log² n)，报告最坏O(log² n+z)。利用子表归并可以在O(n log n)建立关联表；若对每个节点的表独立重新排序，不能照抄这个构建界。带分数级联的更强查询界属于额外变体，本文没有实现。

k-d树采用另一种取舍：交替按坐标方向划分空间，每次按中位数保持平衡。查询矩形与某子区域无交则跳过，完全包含则报告子树，部分相交才继续下降。对平衡二维树，在标准正交范围报告条件下，可得到最坏O(√n+z)查询、O(n)空间。这个界依赖平衡划分和固定维数，不适用于任意插入顺序长成的退化树。

范围树把点复制到多个关联表中；k-d树通过空间区域剪枝，最坏可能访问更多边界子区域。它们支持预处理后到来的在线静态查询，但不能由“静态可查询”推出“动态修改仍有同一成本”。相同坐标的分割与边界归属也需要一致的规则。

可复跑教学检查

实现examples/advanced-algorithms/rectangle_count.py直接导入11篇range_sum.Fenwick，没有建立第二套前缀和接口。压缩坐标通过排序去重，未借助哈希表，以保持上述确定性比较成本口径。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_rectangle_count.py

独立参照逐点检查四个不等式，不调用扫描线或Fenwick。实际执行枚举[-1,1]×[-1,1]格点上长度0到3的点列表，包含重复与不同输入顺序，共820个列表、184500个矩形查询；固定种子20260920的100批随机输入另通过10000次查询。边界覆盖零宽、零高、同坐标、空集和倒置拒绝。真实stdout位于examples/advanced-algorithms/results/rectangle_count.json。

这是有限差分验证，没有运行范围树或k-d树实现，也没有测量在线查询延迟。随机用例的种子用于复跑，不把测试通过的频率当作算法成功概率。

练习

  1. 输入点为[(0,0),(1,1),(1,1),(2,1)]，手算矩形(1,0,2,2)的两个x事件。说明若同x点先插入，两个事件各会多算什么。
  2. 查询必须立即回答，下一条矩形尚未知，点集保持不变。比较朴素扫描、普通二维范围树和平衡二维k-d树的预处理空间与最坏查询成本；把计数和报告分别列出，不把z省略。

参考资料