A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
<|reference_start|>A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation: The binary indexed tree, or Fenwick tree, is a data structure that can efficiently update values and calculate prefix sums in an array. It allows both of these operations to be performed in $O(\log_2 N)$ time. Here we present a novel data structure resembling the Sierpinski triangle, which accomplishes these operations with the same memory usage in $O(\log_3 N)$ time instead. We show this order to be optimal by making use of a connection to quantum computing.<|reference_end|>
@article{harrison2024a,
    title={A Sierpinski Triangle Data Structure for Efficient Array Value Update
  and Prefix Sum Calculation},
    author={Brent Harrison, Jason Necaise, Andrew Projansky, James D. Whitfield},
    journal={arXiv preprint arXiv:2403.03990},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03990},
    primaryClass={cs.DS}
}