FenwickTree
|
Calling Sequence
|
|
F := FenwickTree(x)
RangeSum(F)
RangeSum(F, j)
RangeSum(F, i, j)
AddToUnderlying(F, i, v)
LowerBound(F, p)
|
|
Parameters
|
|
F
|
-
|
Fenwick tree object
|
x
|
-
|
list, Vector, or 1-dimensional Array starting at 1
|
i
|
-
|
integer indices
|
v
|
-
|
any value
|
p
|
-
|
nonnegative value
|
|
|
|
|
Description
|
|
•
|
A Fenwick tree, or binary indexed tree, is a data structure for quickly computing sums of values in an array that undergoes changes. It was proposed by Ryabko [1] and later described by Fenwick [2].
|
•
|
This data structure is implemented in Maple as an object.
|
|
Construction
|
|
•
|
To construct a Fenwick tree, use the command FenwickTree(x). This creates a new Fenwick tree for which the underlying array of values, described below as b, is initialized to the values in x. Note that updating x afterwards has no effect; use the AddToUnderlying command to modify the underlying array of values.
|
|
|
Range sums
|
|
•
|
To compute the sum of b[i .. j], use the command RangeSum(F, i, j). If neither x nor b have been modified since the creation of F, this is equivalent to add(x[i .. j]). Negative indices count from the end. You can omit the starting index (default: 1), so RangeSum(F, j) = RangeSum(F, 1, j). You can also omit the ending index (default: -1), so RangeSum(F) = RangeSum(F, 1, -1); this gives the sum of the whole array.
|
•
|
You can access the current value of b[i] with RangeSum(F, i, i).
|
|
|
Modification
|
|
•
|
To modify b, you can add values to one entry at a time. The command AddToUnderlying(F, i, v) will add v to b[i], just like b[i] += v would do.
|
|
|
Lower bound
|
|
•
|
The values stored in F need not be numeric, but if they are, you can find an index i such that RangeSum(F, i) <= p < RangeSum(F, i+1) for any nonnegative p. If b has n entries, we define RangeSum(F, n+1) = infinity to make this work -- this does not hold in general. Such a value i is returned by the command LowerBound(F, p).
|
|
|
Computational complexity
|
|
•
|
Construction of a Fenwick tree with entries takes elementary operations.
|
•
|
Computing a range sum, modifying an entry, and computing a lower bound all take elementary operations.
|
|
|
|
Examples
|
|
We start by creating a Fenwick tree for the integers from 1 up to 100, in order.
>
|
|
| (1) |
>
|
|
For which i is the sum of 1 up to i just under (or equal to) 2000?
>
|
|
Let's add 1 to each entry.
>
|
|
>
|
|
We can also create a Fenwick tree for objects other than integers that can be added, for example, for vectors.
>
|
|
| (10) |
Computing some 17000 partial sums is much faster if we use a Fenwick tree than if we add up all vectors in this range every time.
>
|
|
memory used=61.17MiB, alloc change=38.00MiB, cpu time=754.00ms, real time=732.00ms, gc time=112.90ms
| |
>
|
|
memory used=1.13GiB, alloc change=54.45MiB, cpu time=4.84s, real time=4.17s, gc time=1.07s
| |
We verify that the sums are pairwise the same.
>
|
|
>
|
|
|
|
References
|
|
|
[1]: Boris Ryabko (1989). A fast on-line code. Soviet Math. Dokl. 39 (3): 533–537.
|
|
[2]: Peter M. Fenwick (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience. 24 (3): 327–336.
|
|
|
Compatibility
|
|
•
|
The FenwickTree package was introduced in Maple 2024.
|
|
|