假设您有k个已排序的数组，每个数组的大小为n。您希望在这k个数组中的每个数组中搜索单个元素(如果它不存在，则搜索它的前身)。
显然，您可以分别对每个数组进行二进制搜索，从而产生运行时。但我们可能认为我们可以做得更好：毕竟，我们正在做同样的搜索k次，也许我们可以重复使用第一次搜索的结果，供以后搜索。
这是我们可以做的另一件显而易见的事：对于第一个数组中的每个元素，让它指向第二个数组中具有相同值的元素(如果值不存在，则为前置元素)。然后，一旦我们在第一个数组中找到了该项，我们就可以顺着这些指针向下查找，以便找出该项在所有其他数组中的位置。
但有一个问题：有时候，这些指针根本帮不了我们。特别是，如果后面的列表完全位于第一个列表的两个元素之间，我们必须重做整个搜索，因为指针没有给我们任何我们不知道的信息。
那我们怎么办？考虑k=2的情况；只要我们能保证第一个列表包含正确的元素，为您提供关于第二个数组的有用信息，一切都会更好。我们可以只合并数组，但是如果我们在一般情况下这样做，我们最终会得到一个完全合并的大小数组，如果k很大，这就不太好了。
但是我们不需要第二个数组的所有元素，其他项目都可以！
让我们反复这样做吧。获取最后一个数组，获取所有其他元素，并将其合并到倒数第二个数组中。现在，使用新的倒数第二个数组，对下一个数组执行此操作。冲洗并重复。第一个数组最终有多大？您可以求解递归：，它是几何级数。令人惊讶的是，新的第一个列表只有两倍大，这只是二进制搜索中的一个额外步骤！
我们刚刚实现的是分数级联！任何阵列的一小部分都会级联到其余阵列。
还有一个细节需要注意。当我向下跟踪指针时，我可能会在一个元素上结束，该元素实际上不是当前数组的成员(它是级联起来的)。我需要能够有效地找到下一个元素，它是当前数组的成员(并且在它和下一个成员元素之间可能会有许多级联元素，因此向左扫描可能需要很长时间)；因此，对于每个级联元素，我都会存储指向前一个成员元素的指针。
分数级联是一种非常有用的转换，用于各种上下文中，包括分层范围树和3D正交范围搜索。事实上，它可以通过几种方式进行推广。第一个是，我们可以级联一些固定分数的元素，而不是我们在这里做的1/2。α。此外，我们不必将自己限制为级联一个数组列表；我们可以级联一个任意图，只要我们选择α小于1/d，就可以将多个列表合并在一起，其中d是节点的步长。
锻炼身体。在此之前，我们描述了范围树。如何使用分数级联将查询复杂度降低1倍？
锻炼身体。实际上，我们可以通过另一种方式在分数级联的数据结构中设置指针。不是每个元素都有向下指针，我们只维护相同元素之间的指针(也就是说，它们是级联的)。事实证明，这在构建数据结构时更加方便。但是，您现在需要维护另一组指针。他们是什么?。(提示：考虑搜索落在非级联成员元素上的情况。)