2025-11-17T04:01:13.190278

Retroactive Monotonic Priority Queues via Range Searching

Castro, de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) and partially retroactive priority queues can cost $O(\log m)$ time per operation. So far, it is unknown whether this $O(\log m)$ bound can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue with a cost of $O(\log m + T(m))$ time per operation, where $T(m)$ is the maximum between the query and the update time of a specific range-searching data structure with $m$ elements. Finally, we design a fully retroactive monotonic priority queue that costs $O(\log m \log \log m)$ time per operation.

academic

Retroactive Monotonic Priority Queues via Range Searching

基本信息

论文ID: 2508.09892
标题: Retroactive Monotonic Priority Queues via Range Searching
作者: Lucas Castro, Rosiane de Freitas (Institute of Computing - UFAM, Brazil)
分类: cs.DS (Data Structures and Algorithms), cs.CG (Computational Geometry)
发表时间: arXiv预印本，2025年10月14日更新
论文链接: https://arxiv.org/abs/2508.09892

摘要

已知最优的完全可追溯优先队列每次操作需要 $O(\log^2 m \log \log m)$ 时间，其中 $m$ 是在数据结构上执行的操作总数。相比之下，标准（非追溯）和部分可追溯优先队列每次操作只需 $O(\log m)$ 时间。目前尚不清楚完全可追溯优先队列是否能达到 $O(\log m)$ 的界限。本文研究单调优先队列这一受限变体，首先证明了在可追溯单调优先队列中查找最小值是范围搜索问题的特例，然后设计了一个每次操作耗时 $O(\log m + T(m))$ 的完全可追溯单调优先队列，最后实现了每次操作耗时 $O(\log m \log \log m)$ 的完全可追溯单调优先队列。

研究背景与动机

问题定义

传统数据结构只能操作"当前"状态，无法查询或修改过去的状态。可追溯数据结构由Demaine等人引入，能够修改过去的状态并将修改的后果传播到当前状态。根据功能不同，可分为：

部分可追溯：可以修改过去，但只能查询当前状态
完全可追溯：既可以修改过去，也可以查询任意时间点的状态

研究动机

效率差距：完全可追溯优先队列与标准/部分可追溯版本存在显著的时间复杂度差距
理论挑战：不清楚完全可追溯优先队列是否能达到 $O(\log m)$ 的理论下界
实际应用：单调优先队列在Dijkstra算法等场景中有重要应用价值

现有方法局限性

最优完全可追溯优先队列时间复杂度为 $O(\log^2 m \log \log m)$
与标准优先队列的 $O(\log m)$ 复杂度存在较大差距
缺乏针对受限变体（如单调优先队列）的专门研究

核心贡献

理论发现：证明了在可追溯单调优先队列中查找最小值等价于范围搜索问题
通用框架：设计了时间复杂度为 $O(\log m + T(m))$ 的完全可追溯单调优先队列，其中 $T(m)$ 是范围搜索数据结构的查询/更新时间
具体实现：基于2D范围树实现了时间复杂度为 $O(\log m \log \log m)$ 的完全可追溯单调优先队列
几何视角：提供了理解可追溯优先队列的新几何视角

方法详解

任务定义

设计支持以下操作的完全可追溯单调优先队列：

Insert(insert(x), t)：在时间 $t$ 插入元素 $x$
Delete(insert(x), t)：删除时间 $t$ 的插入操作
Insert(extract-min, t)：在时间 $t$ 插入提取最小值操作
Delete(extract-min, t)：删除时间 $t$ 的提取操作
GetMin(t)：返回时间 $t$ 的最小元素

单调性约束：提取的元素必须形成非递减序列。

核心理论基础

存在性条件（引理14）

在单调优先队列中，元素 $x$ 在时间 $t$ 存在当且仅当：

insertionTime(x) ≤ t
x > lastExtracted(t)

这避免了维护每个元素的提取时间，简化了追溯操作的复杂性。

最后提取元素的高效查找（引理16-17）

关键洞察：在单调优先队列中，第 $k$ 小的元素 val[k] 只能被第 $k$ 个提取操作 em[k] 提取。

算法：

在提取时间树中找到时间 $t$ 的前驱操作
确定该操作的序号 $k$
返回第 $k$ 小的元素

时间复杂度： $O(\log m)$

几何化表示（引理18）

将单调优先队列表示为2D平面上的点：

每个元素 $e$ 表示为点 (insertionTime(e), e)
GetMin(t) 查询转化为在矩形 $R(t) = (-\infty, t] \times (\text{lastExtracted}(t), \infty)$ 中找到 $y$ 坐标最小的点

这种表示将优先队列查询问题完全转化为几何范围搜索问题。

数据结构设计

三个辅助数据结构：

$T_{el}$ ：存储所有插入元素的顺序统计树
$T_{em}$ ：存储所有提取时间的顺序统计树
$T_{ins}$ ：存储所有 (插入时间, 元素值) 对的最小-y范围搜索数据结构

操作实现：

GetMin(t)：先找到 lastExtracted(t)，然后在 $T_{ins}$ 中查询矩形范围
Insert/Delete(insert(x), t)：更新 $T_{el}$ 和 $T_{ins}$
Insert/Delete(extract-min, t)：更新 $T_{em}$

实验设置

理论分析框架

本文主要进行理论分析，通过以下方式验证方法的正确性：

数学证明：严格证明所有关键引理和定理
复杂度分析：详细分析各操作的时间和空间复杂度
正确性验证：通过几何直观和算法逻辑验证方法正确性

范围搜索数据结构选择

选择Mehlhorn和Näher的2D范围树作为底层数据结构：

更新时间： $O(\log n \log \log n)$ （摊销，可转为最坏情况）
查询时间： $O(\log n \log \log n)$
空间复杂度： $O(n \log n)$

实验结果

主要理论结果

定理20（通用框架）：存在具有以下复杂度的完全可追溯单调优先队列：

提取操作： $O(\log m)$
插入操作： $O(\log m + U(m))$
查询操作： $O(\log m + Q(m))$
空间复杂度： $O(m + S(m))$

其中 $U(m)$ 、 $Q(m)$ 、 $S(m)$ 分别是范围搜索数据结构的更新、查询和空间复杂度。

定理21（具体实现）：基于2D范围树的实现具有以下复杂度：

提取操作： $O(\log m)$
插入操作： $O(\log m \log \log m)$
查询操作： $O(\log m \log \log m)$
空间复杂度： $O(m \log m)$

复杂度比较

数据结构类型	时间复杂度
标准优先队列	$O(\log m)$
部分可追溯优先队列	$O(\log m)$
完全可追溯优先队列（已知最优）	$O(\log^2 m \log \log m)$
本文：完全可追溯单调优先队列	$O(\log m \log \log m)$