梳形构造：多尺度乘积界与混合层高¶

关于单棵树、线性轮数后的候选数量、固定常数倍模板的精确计数，以及为什么该构造仍不超过三次方，另见带图示的梳形树问答。

单前缀乘积界在多个尺度上都能达到同阶¶

不能用一个统一阈值把候选数提前降到线性：不存在绝对常数 \(C\)，使所有森林都满足 \(|P|>Cn\Rightarrow|A(P)|\le Cn\)。

取整数 \(s\ge2\)，令 \(n=4s^2\)。放置 \(2s\) 层梳子，每层主干是一整行道路，所有偶数列向下伸出 \(2s-2\) 格长的齿，相邻层之间留一行空格。它们构成诱导森林。模板也是梳子，宽度为 \(2s^2\)，齿的位置和高度相同。只有模板主干与某层主干对齐、且起始列为偶数的平移合法，所以精确地有

\[ N=8s^4,\qquad |P|=2s^3,\qquad |A(P)|=2s^3+2s. \]

于是 \(|P|/n\) 和 \(|A(P)|/n\) 同时趋于无穷，而 \(|P|\,|A(P)|=\Theta(nN)\)。还可以把宿主改成单一诱导树：删除每层最右侧偶数列的齿，将最右列全部设为道路，以它连接各层主干。此时 \(N=8s^4+2s\)，且 \(|P|=|A(P)|=2s^3\)，反例仍成立。

更一般地，层数取 \(g=\lfloor(n+1)/(h+2)\rfloor\)，齿高为 \(1\le h\le n-1\)，模板宽取 \(\lfloor n/2\rfloor\)。同样得到

\[ N=\Theta(n^2),\qquad |P|=\Theta(n(h+1)),\qquad |A(P)|=\Theta\!\left(\frac{n^2}{h+2}\right). \]

所以单前缀乘积界在从线性到二次方的多个模板尺度上都是紧的。每个高度在这里使用不同的宿主；不能把它们的费用直接累加成同一输入上的对数下界。

混合层高的梳子：按候选存活轮数消去对数¶

上述族也允许在同一张图中混合不同高度。设各层齿高为正整数 \(h_1,\ldots,h_g\)，仍以空行隔开，满足 \(\sum_i h_i+2g-1\le n\)。记

\[ S=\sum_i h_i,\quad H=\max_i h_i,\quad K=|\{i:h_i=H\}|,\quad N=gn+\lceil n/2\rceil S. \]

查询先完成从左向右、宽度为 \(2\le w\le n\) 的模板主干，再以任意交错顺序，把偶数列上的全部齿增长到高度 \(H\)。令

\[ t=\lceil w/2\rceil,\qquad a=\left\lfloor\frac{n-w}{2}\right\rfloor+1. \]

这个限定构造族的严格界是

\[ W\le N+g\sum_{j=1}^{w-1}(n-j)+a(tS-K)\le(2n+1)N. \]

证明如下。完成主干后的候选数为 \(g(n-w+1)\)。首次竖直过滤使奇数列起点全部失败；每层还有 \(a\) 个偶数列起点。高度为 \(h_i\) 的层中，每个这样的起点至多成功检查 \(th_i\) 个齿上新格。若 \(h_i<H\)，再加第一次过深时的一次失败检查；若 \(h_i=H\)，它一直存活。于是主干完成后的总检查量至多为

\[ g(n-w+1)+a(tS-K). \]

加上水平阶段即得第一个不等式。再用 \(g\sum_{j=1}^{w-1}(n-j)\le nN\) 和 \(atS\le nN\)，即得第二个不等式。按高度依次补齐各条齿，可以让第一个不等式取等号。

这证明不同层高的费用由同一张图中的总齿高 \(S\) 共同限制。任意查询、任意分叉森林仍未包括在这个证明内。