{"ID":2882864,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.09892","arxiv_id":"2508.09892","title":"Retroactive Monotonic Priority Queues via Range Searching","abstract":"The best-known fully retroactive priority queue costs $O(\\log^2 m \\log \\log m)$ time per operation and uses $O(m \\log m)$ space, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) priority queues can cost $O(\\log m)$ time per operation and use $O(m)$ space. So far, it remains open whether these bounds 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 that costs $O(\\log m)$ time per operation and uses $O(m)$ space, achieving the same bounds as a standard priority queue.","short_abstract":"The best-known fully retroactive priority queue costs $O(\\log^2 m \\log \\log m)$ time per operation and uses $O(m \\log m)$ space, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) priority queues can cost $O(\\log m)$ time per operation and use $O(m)$ space. So...","url_abs":"https://arxiv.org/abs/2508.09892","url_pdf":"https://arxiv.org/pdf/2508.09892v3","authors":"[\"Lucas Castro\",\"Rosiane de Freitas\"]","published":"2025-08-13T15:50:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\"]","methods":"[]","has_code":false}