View PDF HTML (experimental)

Abstract:We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic $w$-bit word RAM model with special ultrawords of length $w^2$ bits that support standard arithmetic and boolean operation and scattered memory access operations that can access $w$ (non-contiguous) locations in memory. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. The goal in the dynamic range minimum problem is to maintain an array $A$ of $n$ $w$-bit integers subject to range minimum queries (given indices $i$ and $j$ return a smallest integer in the subarray $A[i..j]$) and updates (given index $i$ and integer $\alpha$ set $A[i] \leftarrow \alpha$).
Our main result is a data structure that supports range minimum queries and updates in $O(\log \log \log n)$ time and uses $O(n/\log n)$ space in addition to the input array. This exponentially improves the time of existing techniques. Our result is based on a simple reduction to prefix minimum computations on sequences $O(\log n)$ words combined with a new parallel, recursive implementation of these.

Submission history

From: Philip Bille [view email]
[v1] Mon, 25 Nov 2024 11:02:44 UTC (4,467 KB)
[v2] Fri, 7 Mar 2025 08:36:36 UTC (138 KB)
[v3] Thu, 9 Jul 2026 15:16:44 UTC (38 KB)