Dynamic data structures for twin-ordered matrices

Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis, Wojciech Nadara, Michał Pilipczuk, Karol Węgrzycki, Anna Zych-Pawlewicz

Abstract

We present a dynamic data structure for representing binary $n\times n$ matrices that are $d$-twin-ordered, for a~fixed parameter $d$. Our structure supports cell queries and single-cell updates both in $\Oh(\log \log n)$ expected worst case time, while using $\Oh_d(n)$ memory; here, the $\Oh_d(\cdot)$ notation
BibTeX
@misc{bosek2026dynamic,
  author = {Bartłomiej Bosek and Jadwiga Czyżewska and Evangelos Kipouridis and Wojciech Nadara and Michał Pilipczuk and Karol Węgrzycki and Anna Zych-Pawlewicz},
  title = {{Dynamic data structures for twin-ordered matrices}},
  year = {2026},
  eprint = {2602.18770},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.18770},
}

Loading related content...

Figure