Faster Dynamic Range Mode
share
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 Õ(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.
READ FULL TEXT