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. Our main result is a linear space data structure that supports range minimum queries and updates in \(O(\log \log \log n)\) time. 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Dynamic Range Minimum Queries on the Ultra-wide Word RAM

  • Philip Bille,
  • Inge Li Gørtz,
  • Máximo Pérez López,
  • Tord Stordalen

摘要

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. Our main result is a linear space data structure that supports range minimum queries and updates in \(O(\log \log \log n)\) time. 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.