  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.
