FenwickTree
Calling Sequence
Parameters
Description
Examples
References
Compatibility
F := FenwickTree(x)
RangeSum(F)
RangeSum(F, j)
RangeSum(F, i, j)
AddToUnderlying(F, i, v)
LowerBound(F, p)
F
-
Fenwick tree object
x
list, Vector, or 1-dimensional Array starting at 1
i
integer indices
v
any value
p
nonnegative value
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 n entries takes On elementary operations.
Computing a range sum, modifying an entry, and computing a lower bound all take Ologn elementary operations.
We start by creating a Fenwick tree for the integers from 1 up to 100, in order.
F≔FenwickTreeseq1..100
F≔< a Fenwick tree with 100 entries >
RangeSumF,17,83
3350
add17..83
For which i is the sum of 1 up to i just under (or equal to) 2000?
LowerBoundF,2000
62
RangeSumF,62
1953
RangeSumF,63
2016
Let's add 1 to each entry.
forito100doAddToUnderlyingF,i,1enddo
104
3417
add17..83+83−17+1
We can also create a Fenwick tree for objects other than integers that can be added, for example, for vectors.
l≔seqLinearAlgebra:-RandomVector3,1..1000:
F2≔FenwickTreel
F2≔< a Fenwick tree with 1000 entries >
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.
sums1≔CodeTools:-UsageseqseqRangeSumF2,i,j,j=i..1000,30,i=1..1000:
memory used=61.17MiB, alloc change=38.00MiB, cpu time=754.00ms, real time=732.00ms, gc time=112.90ms
sums2≔CodeTools:-Usageseqseqaddli..j,j=i..1000,30,i=1..1000:
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.
numelemssums1,numelemssums2
17170,17170
andmapi↦EqualEntriessums1i,sums2i,seq1..numelemssums1
true
[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.
The FenwickTree package was introduced in Maple 2024.
For more information on Maple 2024 changes, see Updates in Maple 2024.
Download Help Document
