Fenwick tree
Encyclopedia
A Fenwick tree is a data structure that can be used to implement cumulative frequency tables. It was invented by Peter Fenwick in 1994.
Fenwick trees are typically implemented as arrays.
algorithm, so the operations it supports are guided primarily by the use that it will be put to in the application above.
They can also be used to compute the sum of ranges of consecutive elements in O
(log n) time. With the store (or update) operation taking the same O
(log n) time.
(log n) time:
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.
Structure
A Fenwick tree is a tree that is indexed by the bits of the key for that tree. This tree can only be implemented for keys that are integers and have a fixed range.Fenwick trees are typically implemented as arrays.
Applications
Fenwick trees are used to implement the arithmetic codingArithmetic coding
Arithmetic coding is a form of variable-length entropy encoding used in lossless data compression. Normally, a string of characters such as the words "hello there" is represented using a fixed number of bits per character, as in the ASCII code...
algorithm, so the operations it supports are guided primarily by the use that it will be put to in the application above.
They can also be used to compute the sum of ranges of consecutive elements in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(log n) time. With the store (or update) operation taking the same O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(log n) time.
Supported operations
Fenwick tree supports the following basic operations each of which take OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(log n) time:
- Change the frequency at some position and update the tree
- Read the cumulative frequency for a given key
- Read the actual (not cumulative) frequency at a certain position
- Find the index with a given cumulative frequency, if all individual frequencies are positive, or all indices with a given cumulative frequency, if all individual frequencies are non-negative
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.