2024/03/06 by Brent Harrison, Jason Necaise, Harrison, Brent +5 · 1 citation
Computer Science · #Numerical Methods and Algorithms #Algorithms and Data Compression #Digital Filter Design and Implementation
paper · pdf · doi:10.48550/arxiv.2403.03990
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(log2 N) time. Here we present a novel data structure resembling the Sierpinski triangle, which accomplishes these operations with the same memory usage in O(log3 N) time instead. We show this order to be optimal by making use of a connection to quantum computing.