Southwest Tree: A Low-Memory Data Structure for Partial Accumulations by Non-Commutative Invertible Operations

Nicholas J.C. Papadopoulos · 2025

Read Southwest Tree: A Low-Memory Data Structure for Partial Accumulations by Non-Commutative Invertible Operations by Nicholas J.C. Papadopoulos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-01603.txt.

Description

Nicholas Papadopoulos presents a data structure for adding up parts of a list whose values can change at any time, in a paper from 2025. Two classic structures do this in fast, matched time for both sums and updates. One needs extra memory, and the other fails when the adding step does not commute.

The new structure, called the Southwest Tree, handles non-commuting steps as long as each step can be undone. It matches the classic speed for both sums and updates. It also uses no extra memory beyond the input list itself. Papadopoulos lays out the layout and proves the time bounds. The result suits tasks where order matters, such as combined moves or text edits.

Catalog record

CREATORNicholas J.C. Papadopoulos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-01603

Browse the full library · About the Tower of Babel