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
| CREATOR | Nicholas J.C. Papadopoulos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-01603