en>Ninkazu: /* Induction-Recursion */

2014-01-19T22:22:54Z

Induction-Recursion

New page

A '''Fenwick tree''' or '''binary indexed tree''' is a data structure providing efficient methods for calculation and manipulation of the [[prefix sum]]s of a table of values. It was proposed by [[Peter Fenwick (computer scientist)|Peter Fenwick]] in 1994.<ref>{{cite journal |author=Peter M. Fenwick |title=A new data structure for cumulative frequency tables |journal=Software: Practice and Experience |volume=24 |issue=3 |year=1994 |pages=327–336 |doi=10.1002/spe.4380240306 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917}}</ref> Fenwick trees primarily solve the problem of balancing prefix sum calculation efficiency with element modification efficiency. The efficiency of these operations comes as a trade-off - greater efficiency in prefix sum calculation is achieved by pre-calculating values, but as more values are pre-calculated more must be re-calculated upon any modification to the underlying value table. Fenwick trees both calculate prefix sums and modify the table in <math>O(\log n)</math> time, where <math>n</math> is the size of the table.

==Description==
Given a table of elements, it is sometimes desirable to calculate the [[running total]] of values up to each index according to some [[Associative property|associative]] [[binary operation]] (addition on integers, for example). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value table and having all further queries reflect those changes. Although Fenwick trees are [[Tree (data structure)|trees]] in concept, in practice they are implemented using a flat array analogous to implementations of a [[binary heap]]. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through [[bitwise operation]]s on the [[Binary numeral system|binary]] representation of its index. Each index contains the pre-calculated sum of a section of the table, and by combining that sum with section sums encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all section sums which contain the modified value are in turn modified during a similar traversal of the tree. The section sums are defined in such a way that queries and modifications to the table are executed in asymptotically equivalent time - <math>O(\log n)</math> in the worst case.

The initial process of building the Fenwick tree over a table of values runs in <math>O(n \log n)</math> time. Other efficient operations include locating the index of a value if all values are positive, or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in <math>O(n)</math> time. The sum of an arbitrary subarray can also be calculated by subtracting the prefix sum before its start point from the prefix sum at its end point.

==Applications==
Fenwick trees are used to implement the [[arithmetic coding]] algorithm. Development of operations it supports were primarily motivated by use in that case.

Using a Fenwick tree it is very easy to generate the cumulative sum table. From this cumulative sum table it is possible to calculate the summation of the frequencies in a certain range in order of <math>O(\log n)</math>.

Fenwick tree can also be used to update and query ranges in multidimensional arrays with complexity <math>O(2^d* \log ^d n)</math>, where d is number of dimensions and n is the number of elements along each dimension. <ref>{{cite journal |author=Pushkar Mishra |title=On Updating and Querying Sub-arrays of Multidimensional Arrays |year=2013 |pages=1-5 |url=http://arxiv.org/abs/1311.6093}}</ref>
{{See also|Prefix sums#Applications|l1=Applications of Prefix sums}}

==See also==
* [[Prefix sums]]
* [[Segment tree]]

==References==
<references/>

==External links==
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees A tutorial on Fenwick Trees on TopCoder]
* [http://www.algorithmist.com/index.php/Fenwick_tree An article on Fenwick Trees on Algorithmist]
* [http://michaelnielsen.org/polymath1/index.php?title=Updating_partial_sums_with_Fenwick_tree An entry on Fenwick Trees on Polymath wiki]
* [http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree Order-statistics tree, a related data structure]

{{CS-Trees}}

[[Category:Trees (data structures)]]

Inductive type - Revision history

en>Ninkazu: /* Induction-Recursion */