A compact tree, also called a binary indexed tree, that supports prefix-sum queries and point updates over an array in logarithmic time using less memory and simpler code than a full segment tree.
Facts
Core PrincipleStores partial sums in an array indexed by position so both a prefix sum and a point update can be computed in logarithmic time by walking indices reached through the lowest set bit of the index. 1 Connections
Sources
1. Wikipedia: Fenwick Tree
Wikimedia FoundationLead section, history sentences
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.
Lead section, first sentence
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.
View the Source Frequently Asked Questions
How does a Fenwick tree perform updates and queries in logarithmic time?
It stores partial sums indexed by position and walks indices found through the lowest set bit, so each query or update touches only a logarithmic number of positions.
A Fenwick tree stores partial sums in an array indexed by position, so both a prefix sum and a point update can be computed in logarithmic time by walking indices reached through the lowest set bit of the index. This bit trick lets the tree answer a running total or apply a change by touching only a logarithmic number of positions, instead of walking every element in the array.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.