Fenwick tree
A Fenwick tree (also known as binary indexed tree) is a data structure that can be used to implement cumulative frequency tables. It was invented by Peter Fenwick in 1994. [1]
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 coding algorithm, so the operations it supports are guided primarily by the use that it will be put to in the application above.
Supported operations
Fenwick tree supports the following basic operations each of which take O(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
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.
References
- ^ Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience. 24 (3): 327–336. doi:10.1002/spe.4380240306.