一、overview第2页解答了两个问题“这一整章要解决什么物理问题”和“用什么工具去解决”1. 这一章要解决的核心物理问题几何对象之间的相交检测PPT 的原话是“Intersections among geometric objects.”几何对象之间的交点/重叠。具体拆分为两个核心任务2D 正交范围搜索2d orthogonal range search在平面上给你一堆点画一个矩形框框住的所有点都要找出来。正交矩形相交orthogonal rectangle intersection给你一堆边与坐标轴对齐的矩形找出所有互相重叠的矩形对。应用场景PPT 列了 CAD计算机辅助设计、游戏、电影、虚拟现实、数据库、GIS地理信息系统。在 DFT 领域虽然 PPT 没明说这直接对应芯片版图设计规则检查DRC——需要检查不同金属层上的导线是否间距不足或本不该相交的线网是否意外短路。这就是几何相交检测在物理设计中的直接映射。2. 高效解决方案的核心工具二叉查找树及其扩展PPT 最后一行是“Efficient solutions. Binary search trees (and extensions).”高效解决方案。二叉查找树及其扩展。物理含义一维1D问题直接用你刚学完的 BSTrank 剪枝遍历就能解决数轴上的范围查找。二维2D问题直接把 BST 的思想“升维”用扫描线Sweep Line把二维问题“压扁”成一维问题然后用 BST 处理比如线段相交、矩形相交。用空间划分树kd-tree直接在二维平面上递归分割平面代替 BST 在数轴上的二分查找。这一讲的前后脉络你刚刚学完的第 3 章查找教会了你如何管理一个“键”序列1D 有序数据。而这一章几何搜索是在问你“如果键变成了平面上的点2D或者键变成了区间Interval之前学过的 BST 还能不能改一改继续用”答案是核心数据结构还是 BST只是把比较的规则从“数字大小”改成了“空间位置关系”或“端点坐标顺序”。第 2 页的概览已经直接告诉你了整章的物理动作都是 BST 指针操作的变体只不过比较的对象从key变成了x/y坐标或区间的左右端点。Q哦天这个看起来好复杂你可以给一点点提示或者是铺垫一下吗在我们正式进入内容之前。A1. 扫描线算法Sweep Line不是在算几何是在做“时间排序”物理本质把“空间平面”变成“时间线”。想象一条竖直线扫描线从平面最左边开始匀速向右移动。空间中的x坐标就变成了这条扫描线上的“时间刻度”。当扫描线经过一个左端点时相当于“时间到了”把这个物体的y坐标插入到 BST 中你已经在符号表里插入过无数次了。当扫描线经过一个右端点时相当于“时间过了”把这个物体的y坐标从 BST 中删除你刚学完 BST 的删除。当扫描线遇到一条竖直线段时在 BST 里做一次1d range search你刚在一节学完的区间查找。你只需要做三件事插入、删除、范围查找。全是 BST 的基本操作。没有任何新数据结构。“降维”在哪里二维空间的交点问题被拆解成“沿着一条线移动”的一维时间序列问题。2. Kd-tree不是在画平面是在做“交替比较”物理本质把 BST 的“一维大小比较”改成“交替比较 x 和 y”。标准 BST根节点比较key的大小决定往左还是往右。Kd-tree2维版本根节点比较x坐标小的往左大的往右。下一层子节点比较y坐标小的往左大的往右。再下一层比较x坐标……如此交替。内存结构节点依然是left和right指针和你 BST 一模一样的物理布局。每个节点存一个点Point2D对象。只是比较函数从key.compareTo变成了(depth % 2 0) ? compareX : compareY。“升维”在哪里BST 的递归是“大小二分”Kd-tree 的递归是“左右/上下交替二分”。你依然在递归下降依然在挂载子节点只是判断条件多了一个“奇偶层”。你现在的真实状态你完全没有引入新数学也没有引入新数据结构还是那套左/右指针 递归回溯。你只是把比较的对象从“一个数字”换成了“一个点的 x 或 y”或者把处理方式从“静止查找”变成了“扫描线动态插入删除”。你比 80% 只看概念的人更有优势因为你已经知道 BST 的指针是怎么接上的。剩下要做的只是把put里的cmp key.compareTo(x.key)改成cmp point.compareX(x.point)或者cmp y.compareTo(x.y)。语法比你想象的要简单得多。你准备好了我们就从1d range search后面的第一张line segment intersection开始逐页走。二、1d range search这一节本质上是“把 BST二叉查找树从‘精确查找’扩展为‘范围查找’”。它的物理目标是在有序的键集合中快速找出落在区间 [lo, hi] 内的所有键并统计个数。Page 4定义与几何解释物理内容1D 范围查找是“有序符号表Ordered Symbol Table”的扩展。支持插入、删除、查找标准 BST 操作。范围查找Range Search找出所有满足lo ≤ key ≤ hi的键。范围计数Range Count统计满足条件的键的数量。几何映射把每个键想象成直线数轴上的一个点。范围查找就是在数轴上画一个区间 [lo, hi]找出所有落在这个区间内的点。物理意义处理“所有在某个区间内的元素”的问题本质上是利用 BST 的中序遍历天然有序性升序只截取中间的一段。Page 5初级实现对比这张表告诉你为什么必须用 BST而不是简单结构数据结构插入范围计数范围查找无序链表1NN有序数组Nlog NR log N理想/目标log Nlog NR log N物理断层无序链表插入快头插但查找范围时你必须遍历整个链表检查每个键是否在区间内无法提前退出。有序数组虽然查找很快二分定位lo和hi但插入需要移动大量元素O(N)。它的范围查找本身快但静态维护代价太高。你刚学完 BST应该立刻能看出BST 既支持快速插入~1.39 log N又天然支持顺序遍历正是解决 1D 范围查找的理想结构。Page 6范围计数BST 实现物理动作范围计数size(lo, hi)不需要遍历所有在区间内的键它只需要通过rank函数计算索引差。rank(hi)返回小于hi的键的数量即hi在有序序列中的位置。rank(lo)返回小于lo的键的数量。如果hi存在于树中那么rank(hi) - rank(lo) 1就是闭区间[lo, hi]内的元素个数。如果hi不存在则rank(hi) - rank(lo)即可因为rank返回的是小于该键的数量。时间复杂度rank执行一次二分查找路径长度等于树高~log N。两次rank相加总体成本O(log N)。物理上你只访问了两条路径去找lo和hi的插入位置不需要触碰中间的所有节点。Page 7范围查找递归遍历物理动作范围查找不仅需要计数还要返回所有键的具体值。你不能只靠rank算出差值就结束因为你必须把那些节点地址收集起来。代码逻辑递归如果当前节点为null返回。如果当前节点的键x.key大于lo则左子树中可能有符合条件的小键递归搜索左子树。如果当前节点的键x.key在[lo, hi]之间把x.key加入结果集合。如果当前节点的键x.key小于hi则右子树中可能有符合条件的大键递归搜索右子树。剪枝物理原理如果x.key lo那么左子树的所有键都小于x.key lo全部不符合条件直接剪掉左子树不去遍历。如果x.key hi那么右子树的所有键都大于x.key hi全部不符合条件直接剪掉右子树。时间复杂度O(R log N)R 为命中键的数量。物理上你访问的节点数等于从根到lo的路径从根到hi的路径命中的节点本身。中间那些被完全排除在区间外的整棵子树你根本不会进入它们的内部。这正是 BST 有序性带来的巨大剪枝收益——相对于遍历整个数组的O(N)BST 的处理开销只与你搜索的两条边界路径以及匹配结果的数量相关。你现在对 1D 范围查找的物理逻辑计数靠rank查找靠剪枝递归有任何不清楚的地方吗如果清楚了我们可以继续看下一节line segment intersection线段交点它会用到一个“扫描线Sweep Line”算法把 2D 问题降维成你现在刚学完的 1D 范围查找。三、时间复杂度Q给我仔细解释一下这张表格里面的时间复杂度吧我觉得我还有一些疑惑。A这张表格的困惑点通常集中在“为什么range count和range search在同一个数据结构里复杂度会不一样”以及“为什么R log N里的R去掉不了”我直接从物理动作上给你拆开你就不再迷惑了1. 无序链表Unordered list插入Insert 1物理上你只需要把新节点挂在链表头部改一次next指针。O(1)。范围计数 / 范围查找Count Search N因为链表没有按大小排序。你要找出落在[lo, hi]之间的所有键物理上你必须从头走到尾检查每一个节点的键是否在区间内。你没法“跳过”任何一个节点因为你不知道后面会不会有符合条件的。所以即使只为了数个数range count你也得遍历N个节点。Count 和 Search 在这里物理动作完全一样都是遍历只是最后一个是count一个是print。2. 有序数组Ordered array插入Insert N物理上为了保持数组有序你必须在中间腾出空位需要把插入点后面的所有元素整体向右平移System.arraycopy。平均移动N/2个元素所以是O(N)。范围计数Range count log N物理上不需要触碰区间内的元素。你只需要做两次二分查找log N一次找lo的插入位置一次找hi的插入位置。拿到两个索引后直接用下标相减rank(hi) - rank(lo)就得出了个数。数组中那些元素还没被碰过就已经算出了总数。范围查找Range search R log N计数不需要碰元素但查找需要把它们“拿出来”。物理上你必须从lo的位置开始一个一个地顺着数组往后走直到走过hi的位置。你碰到了R个符合条件的元素所以必须付出R的线性成本。无论数据结构多先进只要你要把R个结果打印出来或返回给调用者你就不可能低于O(R)。3. 目标/理想Goal / BST表格里的“Goal”就是你刚学完的二叉查找树BST。插入log N沿着树高走一遍挂载新节点。O(log N)。范围计数log N利用rank函数二分查找风格的树下降拿到小于lo和hi的节点数相减即可。不需要触碰 R 个节点。范围查找R log N你沿着树找到lo花费log N然后进行中序遍历只输出落在区间内的节点。你触碰了R个节点来输出它们。R这个成本是物理输出代价任何数据结构都省不掉。4. 你最大的疑惑点可能在于“为什么有序数组的 Search 是R log N但 Count 只是log N”因为“数数”和“拿出来”是两件物理上完全不同的事数数Count只需要两个索引值指针或下标算一下减法就有了根本不用去访问中间那些数据。拿出来Search必须把地址或值传递给调用者比如放进队列这意味着 CPU 必须沿着内存地址去触碰这R个对象。触碰R个对象就要花R的时间。这就是为什么 PPT 的表格里R永远不会出现在range count那一列但必定出现在range search那一列。它代表的是物理上输出结果所需的最小代价。Q明白了我刚刚还在想为什么range count不是N/2呢原来是略写。以及我能够明白想要弄二叉搜索树的一片好意但是二叉搜索树由于是地址的跳转最后并不会比数组更慢吗A是的在“纯粹查找只读不写”的场景下有序数组绝对比二叉搜索树BST快得多。而且是数量级的快。但为什么我们还要用 BST甚至不惜学习复杂的红黑树因为你的判断是对的但适用场景完全不同。从物理硬件和操作代价两方面帮你拆开这个矛盾1. 为什么“纯查找”时数组碾压 BST物理原因缓存命中率数组连续内存当你访问arr[0]时CPU 不仅会把arr[0]的值读入缓存还会把相邻的几十个元素缓存行通常 64 字节一起读进高速缓存。当你在有序数组里做二分查找时虽然逻辑上你在“跳着访问”但因为数组紧密排列arr[mid]大概率就在刚刚加载进来的那个缓存行附近。命中缓存极快~1ns。BST链式节点每个Node对象在堆上通过new分配内存地址是分散的即使你插入的顺序是随机的它们在物理内存上也几乎不可能相邻。当你在 BST 中做查找时每次从根节点跳到左子节点或右子节点本质上都是在访问一块全新的、远距离的堆内存地址。CPU 无法预知下个节点的地址导致频繁的缓存未命中Cache Miss需要去主存取数据~100ns慢了近两个数量级。结论如果数据是静态的只查找不插入/删除数组不仅简单而且因为缓存的天然优势它跑得比任何树结构都快。2. 那为什么算法课要死磕 BST动态维护的代价因为数组有一个致命的物理缺陷插入和删除太昂贵。数组插入/删除为了保持有序每次插入或删除你都必须移动平均N/2个元素。在 EDA电子设计自动化工具中如果你正在处理一个动态变化的网表比如扫描线算法扫描线移动时不断插入新的线段y坐标又不断删除旧的用数组就意味着每移动一次扫描线你可能就要在内存里搬运几十万个double数据。这是平方级的时间会直接卡死。BST 插入/删除虽然它跳转地址导致缓存未命中但它的插入和删除只改变路径上的几个指针O(log N)。付出的代价是内存跳转带来的延迟但避免了一次搬运几十万个数据的灾难。3. 回到你刚刚问的这张 PPT几何搜索你即将学习的“扫描线算法Sweep Line”正是这个“动态维护”的经典例子扫描线从左向右移动时BST 里的数据y坐标是在不断动态变化的——左边端点来了就插入右边端点到了就删除。如果这里使用有序数组每一次插入/删除都会导致大规模的数据平移整体复杂度会退化为N²。而 BST 虽然每个节点的访问比数组慢因为缓存不友好但它避免了大量数据的整体搬移把整体的时间复杂度稳定在了N log N。你的直觉是对的在硬碰硬的连续内存读取上数组是王。但算法课教 BST 是因为在动态变化的数据集上树结构用“指针跳转”的代价换取了“避免大规模内存搬运”的收益。在 EDA 处理千万门级电路时避免O(N)的数据平移远比减少缓存未命中重要得多。Q确实如此你这么一说我觉得是该用binary search trees了我想大概是因为我脑海中的总还是小数据模型我想的是维护一个数组可能只有100或几百来个数据。A当N只有几百时你的直觉是完全正确的。在这个规模下数组的搬运成本几百个指针或double的拷贝耗时在微秒级。BST 的缓存未命中每次指针跳转都可能触发一次主存访问~100纳秒树高大概 8-10 层累积的延迟~1微秒反而大于数组平移的耗时。数组在这时确实是王者。临界点在哪为什么你以后再也回不去“小数据”在 EDA芯片设计领域你处理的网表规模是百万门级。我们直接看一个具体的物理量级对比数组插入成本在有序数组中插入平均要移动N/2个元素。当N 10^6时一次插入就是50万次内存拷贝。如果扫描线算法要对百万个事件各做一次插入那就是10^6 * 10^6 / 2 5 × 10^11次内存搬运这在物理上无法在可接受时间内完成。BST 插入成本只沿着树高~log2(10^6) ≈ 20层做指针跳转和赋值。一次插入只涉及 20 次 左右的内存访问。即使每次都有缓存未命中~100ns总的增量时间也只有20 * 100ns 2微秒。同样是百万次操作总耗时只有几秒。分界线当N超过几千时数组的“数据搬运”总耗时就会开始超过 BST 的“指针跳转”总耗时。而当你面对百万级数据时BST 的效率优势是几千倍的。你脑海里之所以还是“小数据模型”是因为平时的编程练习和作业通常只涉及几百个数据。但工业界的工具尤其是你们组做的静态学习、ATPG一旦跑起来内存里装的都是几百万个门节点。到那时你会直观地感受到“哪怕是一次O(N)的遍历都会带来可感知的卡顿”。而你此刻正在建立的 BST 直觉正是为了应对那个场景而提前做的准备。