FenwickTree - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

Home : Support : Online Help : FenwickTree

FenwickTree

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

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 n entries takes On elementary operations.

• 

Computing a range sum, modifying an entry, and computing a lower bound all take Ologn elementary operations.

Examples

We start by creating a Fenwick tree for the integers from 1 up to 100, in order.

FFenwickTreeseq1..100

F< a Fenwick tree with 100 entries >

(1)

RangeSumF&comma;17&comma;83

3350

(2)

add17..83

3350

(3)

For which i is the sum of 1 up to i just under (or equal to) 2000?

LowerBoundF&comma;2000

62

(4)

RangeSumF&comma;62

1953

(5)

RangeSumF&comma;63

2016

(6)

Let's add 1 to each entry.

forito100doAddToUnderlyingF&comma;i&comma;1enddo

104

(7)

RangeSumF&comma;17&comma;83

3417

(8)

add17..83+8317+1

3417

(9)

We can also create a Fenwick tree for objects other than integers that can be added, for example, for vectors.

lseqLinearAlgebra:-RandomVector3&comma;1..1000&colon;

F2FenwickTreel

F2< a Fenwick tree with 1000 entries >

(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.

sums1CodeTools:-UsageseqseqRangeSumF2&comma;i&comma;j&comma;j=i..1000&comma;30&comma;i=1..1000&colon;

memory used=61.17MiB, alloc change=38.00MiB, cpu time=754.00ms, real time=732.00ms, gc time=112.90ms

sums2CodeTools:-Usageseqseqaddli..j&comma;j=i..1000&comma;30&comma;i=1..1000&colon;

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

(11)

andmapiEqualEntriessums1i&comma;sums2i&comma;seq1..numelemssums1

true

(12)

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.

• 

For more information on Maple 2024 changes, see Updates in Maple 2024.


Download Help Document