Fenwick tree

Common card · No. 256614

A Fenwick tree or binary indexed tree (BIT) is a data structure that stores an array of values and can efficiently compute prefix sums of the values and update the values. It also supports an efficient rank-search operation for finding the longest prefix whose sum is no more than a specified value. Its primary use is operating on the cumulative distribution function of a statistical frequency table which is updated often. This structure was proposed by Boris Ryabko in 1989 with a further modification published in 1992. It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article. A simple array of values is trivial (constant-time) to update but requires O ( n ) {\displaystyle O(n)} time to compute a prefix sum or search for a prefix length. An array of prefix sums can return a prefix sum in constant time, and search for a prefix length in...

Read on Wikipedia · Image Jolynecujoh125, CC BY-SA 4.0