Scaled Fenwick Trees

Abstract

A novel data structure that enables the storage and retrieval of linear array numeric data with logarithmic time complexity updates, range sums, and rescaling is introduced and studied. Computing sums of ranges of arrays of numbers is a common computational problem encountered in data compression, coding, machine learning, computational vision, and finance, among other fields. Efficient data structures enabling $\log n$ updates of the underlying data (including range updates), queries of sums over ranges, and searches for ranges with a given sum have been extensively studied ( $n$ being the length of the array). Two solutions to this problem are well-known: Fenwick trees (also known as Binary Indexed Trees) and Segment Trees. The new data structure extends the capabilities for the first time to further enable multiplying (rescaling) ranges of the underlying data by a scalar as well in $\log n$ . Scaling by 0 can be enabled, with the effect that subsequent updates may take $(\log n)^{2}$ time. The new data structure introduced here consists of a pair of interacting Fenwick tree-like structures, one of which holds the unscaled values and the other of which holds the scalars. Experimental results demonstrating performance improvements for the multiplication operation on arrays from a few dozen to over 30 million data points are discussed. This research was done as part of Ajna Labs in the course of developing a decentralized finance protocol. It enables an efficient on-chain encoding and processing of an order book-like data structure used to manage lending, interest, and collateral.

Keywords

• Cumulative sums
• Fenwick trees
• partial sums
• prefix sums
• segment trees