A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation

Abstract

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.

8 pages, 4 figures