分散层叠算法 Fractional Cascading

最近新学了一个有意思的冷门算法,主要解决多个有序序列上的在线查询问题。

问题

简单来说,对多个有序的序列询问多次,每次询问一个数字,给出它在每个序列中的位置。

一个具体的题目,来自 洛谷 P6466

给定 $k$ 个长度均为 $n$ 的、元素互不重复的、严格递增的数组 $L_i$,询问 $q$ 次。每次询问时输入一个数字 $x$, 要求查出 $x$ 在每个数组中的非严格后继(满足 $\ge x$ 的最小的元素 ),输出这些后继元素的异或和。

注意,本文中的数组下标均从 $1$ 开始。

前置讨论

首先,最简单的思路是,依次对每个数组二分,每次询问的时间复杂度是 $O(k\log{n})$。对于多次询问的话,这种思路时间上比较吃亏。

另一种思路是,先预处理一下,把这些数组归并成一个大的有序数组,然后其中每一项再存一个长度为 $k$ 的数组 $C$, 其中 $C_i$ 表示这个元素在原数组 $L_i$ 中的后继位置。

实际上就是一个 $kn \times k$ 大小的二维表格,当我们查询时,只需要对大数组二分,然后取出命中的一行的 $C_i$ 数组即可。

这种做法的每次询问的时间复杂度是 $O(\log{kn} + k)$ ,包括二分的时间和取出结果的时间。但是,空间复杂度是比较大的 $O(kn\times k)$。

分散层叠算法

相比前面的两种方法来说,分散层叠算法 (Fractional Cascading) 的优秀之处在于,可以做到 $O(\log{n} + k)$ 的时间复杂度 和 $O(kn)$ 的空间复杂度。

同样是分为两个过程:预处理 和 在线查询。

预处理

预处理的过程是,构造 $k$ 个有序的辅助数组 $M_i$。首先,最后一个数组 $M_k$ 直接采用原数组 $L_k$。 然后 从后向前构造,也就是说,知道 $M_{i+1}$ 的情况下,去构造 $M_i$。 具体的方式是,对 $M_{i+1}$ 进行间隔采样(就是每隔一个元素取一个),然后和 $L_i$ 进行归并,得到 $M_i$。

同时,对于 $M_i$ 中的每个元素,除了要记录元素值 $x$ 本身以外,再额外维护两个信息 $[y,z]$:

  • $y$ 表示数值 $x$ 在 $L_i$ 中的后继位置。
  • $z$ 表示数值 $x$ 在 $M_{i+1}$ 中的后继位置。

看起来有点不好懂,直接来看一个例子。

下图中,$M_i$ 中的每个元素存储的三个字段表达为 $x[y,z]$ 的形式:

  1. 先构造最后的 $M_3$,直接沿用 $L_3$ 即可。

    另外,最后一行的 $M_k$ 中的 $z$ 字段是没有意义的,不会用到。

  2. 然后,对于 $i < k$ 的情况,从位置 $2$ 开始,对 $M_{i+1}$ 间隔采样,再和 $L_i$ 归并,合并过程和归并排序是一样的。
  3. 同时维护好 $y$ 和 $z$ 字段,分别是 $x$ 在 $L_i$ 中后继的位置 和 $M_{i+1}$ 中后继的位置。

    比如说,$M_1$ 中的 $4[2,3]$ 的 $y$ 字段是 $2$,指向 $L_1$ 中的第 $2$ 个元素 $4$。$z$ 字段是 $3$ 指向 $M_2$ 中的第 $3$ 个元素 $8$。

在归并过程中,可以一并维护 $y$ 和 $z$ 字段,这一点可以在后面的 代码实现 中看到。

询问

先研究一下,构造这些辅助数组可以带来的性质。

如果 $x$ 在 $M_i$ 中的后继是 $b[y,z]$,那么 $x$ 在 $M_{i+1}$ 中的后继要么在 $z$ 处,要么在 $z-1$ 处

原因在于:

  1. 首先,$b$ 是 $x$ 的后继,那么肯定有 $x \le b$。
  2. $b$ 指向 $M_{i+1}$ 中的 $z$ 处,那么肯定有 $b \le M_{i+1}[z]$。同时说明 $z$ 处是可能的后继(之一)。
  3. 因为采用间隔采样,所以 $M_{i+1}$ 中位置 $z-2$ 处的值 $a$ 也会在预处理阶段归并到 $M_i$ 中去, 那么肯定 $a \lt x$。这里一定是严格小于的关系,否则与 $x$ 在 $M_i$ 中的后继是 $b$ 这个条件矛盾。
  4. 综合看来,在数组 $M_{i+1}$ 中,$x$ 一定位于区间 $(z-2, z]$ 内,前开后闭。也就是说,$x$ 在 $M_{i+1}$ 中的后继只有两种可能的位置,即 $z-1$ 和 $z$ 。

只需要检查下这两个位置,确切地说,先检查一下 $z-1$ 处元素值和 $x$ 的大小关系,如果满足 $x \le M_{i+1}[z-1]$, 那么 $z-1$ 处就是答案,否则 $z$ 处就是答案。

理清了这一点后,整个查询过程的步骤就简单了。

假设数组 $pos_i$ 表示输入的数字 $x$ 在原数组 $L_i$ 中的后继的位置:

  1. 首先对 $M_1$ 二分,得到后继 $x_1[y_1, z_1]$,即 $pos[1] = y_1$。然后拿着 $z_1$ 进入下面的步骤。
  2. 对于 $i \gt 1$ 的情况,检查 $z-1$ 和 $z$ 处的情况,确认真正的后继位置 $y$。依次进行下去即可。

举一个具体的例子,下图中,要查询的是 $x=4$:

  1. 在 $M_1$ 中二分得到后继 $4[2,3]$,所以 $pos[1] = 2$。
  2. 然后拿着 $z=3$ 在 $M_2$ 中依次检查 $3$ 和 $8$,此时 $z$ 处就是后继,得到 $pos[2]=3$。
  3. 然后拿着 $z=2$ 在 $M_3$ 中依次检查 $5$ 和 $9$,此时 $z-1$ 处才是后继,得到 $pos[3]=1$。

我们可以人工检查一下这答案数组的正确性。

不过,有一种情况,当不存在后继时,需要特判处理

比如说,还是这个例子,查询 $x=9$ 的时候,在 $M_2$ 中 $z=4$ 指向了一个无效位置。事实上,$x=9$ 在 $L_2$ 中不存在后继。

无论如何,我们都可以在查询的时候,检查确认一下后继的合法性

复杂度

首先,先看一下每个辅助数组 $M_i$ 的大小 $SZ_i$。

最后一个 $M_k$ 的大小是 $n$,然后取一半和 $L_{k-1}$ 合并,得到 $M_{k-1}$,其大小是 $n+n/2$。

进一步地,$M_{k-2}$ 的大小会是 $n + SZ_{k-1}/2$,也就是 $n+n/2+n/4$。

依次推导下去,$M_i$ 数组的大小 $SZ_i$ 会是:$n + n/2 + n/4 + … + n/{2^{k-i}}$,不超过 $2n$ [1]

也就是说,每个 $M_i$ 数组的大小肯定不超过 $2n$

因此,整体的空间复杂度会是 $O(k * 2n)$ ,也就是 $O(kn)$,其中 $k$ 是有序原数组的个数、$n$ 是每个数组的大小。

预处理是不断合并 $L_i$ 和 $M_{i+1}$ 的一半来构造 $M_{i}$ 的过程,每次合并是线性的,和归并排序中的合并子过程是一样的, 共进行 $k$ 次,所以时间复杂度是 $O(k*(n+2n/2))$,也就是 $O(kn)$。

每次询问时,先对 $M_1$ 进行一次二分查找,然后再依次向下检查,每个 $M_i$ 中最多检查两个元素,所以 时间复杂度是 $O(\log{n} + k)$

代码实现

思路已经梳理完毕,最后来实现代码。

结构定义
  1. 假定 $k$ 不会超过常数 $K$,$n$ 不会超过常数 $N$,并定义好原始数组 $L_i$。
  2. 辅助数组 $M_i$ 的每一项会存储三个字段 $x[y,z]$,可以定义一个结构体 V
  3. 每个 $M_i$ 数组的大小不会超过 $2n$,所以可以直接定义 $M$ 数组的长度为 $2*N$。
  4. 对于每次查询,用 $ans$ 数组来记录输入的 $x$ 在每个 $L_i$ 中的后继的元素值。

因此结构定义的实现如下:

分散层叠算法 - 结构定义 (C++)
const int N = 10001;
const int K = 101;

int L[K][N];  // 原始的 k 个有序序列, 从下标 1 开始

// M 数组中的每个元素是一个结构体
struct V {
    int x;      // 元素值
    int y = 0;  // 在 L[i] 中出现的位置
    int z = 0;  // 在 M[i+1] 中出现的位置
};

V M[K][2 * N];  // 构造的 k 个序列, 从下标 1 开始
int SZ[K];      // 记录 M[i] 的长度

int ans[K];  // 记录一次询问在每个序列中的答案
合并函数

负责把 $M_{i+1}$ 间隔采样后和 $L_i$ 归并后生成 $M_i$, 这个过程和归并排序[2] 中的合并函数几乎完全一样。 不同点只有两处(我们用 $start1$ 和 $start2$ 分别代表 $L_i$ 和 $M_{i+1}$ 的扫描指针):

  1. 由于是间隔采样,所以 $M_{i+1}$ 的指针 $start2$ 要以步长 2 来递进。
  2. 但是步长 2 有可能会导致错过真正的后继

第二点非常细腻,我们知道在合并过程中,对于当前要考虑的槽位,要么取 $L_i$ 的元素,要么取 $M_{i+1}$ 的元素,这要看哪一方更小。

当 $L_i$ 中的元素更小时,它要记录的 $z$ 字段不能简单的采用 $start2$ 的值,因为 $start2$ 是按步长 $2$ 走的,它可能跳过 $L_i[start1]$ 的真正的后继。 比如下图中就是一个例子。这时候要检查一下 $start2-1$ 的情况,从 $start2-1$ 和 $start2$ 中挑选一个作为 $z$ 的取值。

但是当 $M_{i+1}$ 中的元素更小时,就是说考虑这个槽位放入 $M_{i+1}[start2]$ 时,则不必处理这个问题,因为它的后继肯定是 $start2$。

合并函数的实现代码如下:

分散层叠算法 - 合并函数 (C++)
// 把 M1 每隔一个元素取样, 然后和 Li 归并到 M2 中去
// Li 的起始结束是 start1, end1; M1 的起始结束是 start2, end2
// M2 的起始是 start; 返回 start, 即最终 M2 的大小
int merge(int *Li, V *M1, V *M2, int start1, int end1,
                                 int start2, int end2,
                                 int start) {
    auto take1 = [&]() {  // 取 Li 的数值
        M2[start].x = Li[start1];
        M2[start].y = start1;
        // 注意这里,为了防止 M1 的步长为 2 导致错过真正的后继,需要检验下
        // start2-1 位置是否是真的后继
        M2[start].z = M1[start2 - 1].x >= Li[start1] ? (start2 - 1)
                                                     : start2;
        start++;
        start1++;
    };
    auto take2 = [&]() {  // 取 M1 的数值
        M2[start].x = M1[start2].x;
        M2[start].y = start1;
        M2[start].z = start2;
        start++;
        start2 += 2;  // 间隔取样
    };
    while (start1 <= end1 && start2 <= end2)
        Li[start1] <= M1[start2].x ? take1() : take2();
    while (start1 <= end1) take1();
    while (start2 <= end2) take2();
    return start;
}
预处理函数

预处理过程的思路清楚后,实现就比较简单了:

分散层叠算法 - 预处理函数 (C++)
void preprocess() {
    memset(M, 0, sizeof(M));
    memset(SZ, 0, sizeof(SZ));

    // M[k] 即 L[k] 序列本身
    for (int j = 1; j <= n; j++) {
        M[k][j].x = L[k][j];
        M[k][j].y = j;
    }

    // 自后向前, 归并 M[i+1] 的一半和 L[i] 来构造 M[i]
    SZ[k] = n;
    for (int i = k - 1; i > 0; --i) {
        // start2: 从 2 开始间隔采样
        // 最终大小是 start2-1
        SZ[i] = merge(L[i], M[i + 1], M[i], 1, n, 2, SZ[i + 1], 1) - 1;
    }
}

这里有一个细节点:为什么从位置 2 开始采样,而不是直接从位置 $1$ 开始呢? 一个好处是,这样在处理查询时,考虑 $z-1$ 位置上的元素时,就不必考虑其合法性了。

询问函数

函数 query(int x) 会把 $x$ 在每个数组 $L_i$ 中的后继元素的值写在 $ans[i]$ 上。

首先,对 $M_1$ 进行二分查找,属于二分求 $\ge x$ 的左界 [3]

int l = 1, r = SZ[1];
while (l < r) {
   int m = (l + r) >> 1;
   if (M[1][m].x >= x) r = m;
   else l = m + 1;
}

此时,l 就是 $x$ 在 $L_1$ 中的后继的位置。第一轮的目标 $v$ 就是 $M[1][l]$ 了:

V *v = &M[1][l]; // 取的指针

但是,要时刻注意确认后继的有效性

// 注意验证合法性, 有可能不存在后继
if (v->x >= x) ans[1] = L[1][v->y];

和前面分析的思路一样,对于后续 $i>1$ 的情况,拿着 $z$ 不断一层一层的找就可以了,对于每一层,都只需确认两个位置,即 $z-1$ 和 $z$ 处。

for (int i = 1; i < k; i++) {
    // 考察 z-1 处, 注意 z 超过 M[i+1] 大小的情况
    if (M[i + 1][v->z - 1].x >= x || v->z > SZ[i + 1])
        v = &M[i + 1][v->z - 1];
    else // 否则就是 z 处
        v = &M[i + 1][v->z];
    // 但是要注意验证后继的合法性
    if (L[i + 1][v->y] >= x) ans[i + 1] = L[i + 1][v->y];
}

其他关于 洛谷 P6466 题目具体相关的代码不必再说明, 完整代码实现见:code-snippets - 分散层叠算法 - P6466

结尾语

洛谷 P6466 题目中约定了元素互不重复、每个数组严格递增的条件,但是,分散层叠算法并不要求原数组是严格有序的。

最后,这个算法还挺有意思的,时间复杂度和空间复杂度都很优秀。但是代码实现起来其实也并没有那么简洁~

(完)

本文原始链接地址: https://writings.sh/post/fractional-cascading

王超 ·
喜欢这篇文章吗?
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅