Faster Dynamic Range Mode
Faster Dynamic Range Mode
复制标题
更快的动态范围模式
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yinzhan Xu
中科院分区：
文献类型：
--
作者：
Bryce Sandlund;Yinzhan Xu
在动态范围模式问题中，我们给出了一个由$ n $界定的序列$ a $的长度，并要求插入元素插入，删除和查询，以了解$ a $的连续子序列的最常见元素。在这项工作中，我们设计了一个确定性数据结构，该结构在最差的案例中处理每个操作$ ilde {o}（n^{0.655994}）$ time，从而破坏$ o（n^{2/3}）$ per-此问题的操作时间障碍。通过将Williams和XU中的想法（SODA 2020）与最小产品的新型数据结构变体相结合，可以实现数据结构。
In the dynamic range mode problem, we are given a sequence $a$ of length bounded by $N$ and asked to support element insertion, deletion, and queries for the most frequent element of a contiguous subsequence of $a$. In this work, we devise a deterministic data structure that handles each operation in worst-case $ ilde{O}(N^{0.655994})$ time, thus breaking the $O(N^{2/3})$ per-operation time barrier for this problem. The data structure is achieved by combining the ideas in Williams and Xu (SODA 2020) for batch range mode with a novel data structure variant of the Min-Plus product.