FenwickTree class

A fenwick tree (or binary indexed tree) is a data structure that can efficiently update and calculate sums in an array of values.

See https://en.wikipedia.org/wiki/Fenwick_tree.

Mixed-in types
Available extensions

Constructors

FenwickTree(int length)
Constructs a Fenwick tree with the given length.
FenwickTree.of(Iterable<int> iterable)
Constructs a Fenwick tree from the values of iterable in O(n).
factory

Properties

first → int
The first element.
no setterinherited
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Whether this collection has no elements.
no setteroverride
isNotEmpty → bool
Whether this collection has at least one element.
no setterinherited
iterator → Iterator<int>
A new Iterator that allows iterating the elements of this Iterable.
no setteroverride
last → int
The last element.
no setterinherited
length → int
The number of elements in this Iterable.
no setteroverride
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
single → int
Checks that this iterable has only one element, and returns that element.
no setterinherited

Methods

any(bool test(int element)) → bool
Checks whether any element of this iterable satisfies test.
inherited
cast<R>() → Iterable<R>
A view of this iterable as an iterable of R instances.
inherited
contains(Object? element) → bool
Whether the collection contains an element equal to element.
inherited
elementAt(int index) → int
Returns the indexth element.
inherited
every(bool test(int element)) → bool
Checks whether every element of this iterable satisfies test.
inherited
expand<T>(Iterable<T> toElements(int element)) → Iterable<T>
Expands each element of this Iterable into zero or more elements.
inherited
firstWhere(bool test(int element), {int orElse()?}) → int
The first element that satisfies the given predicate test.
inherited
fold<T>(T initialValue, T combine(T previousValue, int element)) → T
Reduces a collection to a single value by iteratively combining each element of the collection with an existing value
inherited
followedBy(Iterable<int> other) → Iterable<int>
Creates the lazy concatenation of this iterable and other.
inherited
forEach(void action(int element)) → void
Invokes action on each element of this iterable in iteration order.
inherited
gcd() → int

Available on Iterable<int>, provided by the GcdIntegerIterableExtension extension

Returns the greatest common divisor (GCD) of the values in this Iterable. This is the largest positive integer that divides all numbers.
join([String separator = ""]) → String
Converts each element to a String and concatenates the strings.
inherited
lastWhere(bool test(int element), {int orElse()?}) → int
The last element that satisfies the given predicate test.
inherited
lcm() → int

Available on Iterable<int>, provided by the LcmIntegerIterableExtension extension

Returns the least common multiple (LCM) of the values in this Iterable. This is the smallest positive integer that is divisible by all numbers.
map<T>(T toElement(int e)) → Iterable<T>
The current elements of this iterable modified by toElement.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
prefix(int index) → int
Computes the sum of all values up to index (exclusive) in O(log n).
range(int start, int end) → int
Computes the sum of all values between start and end (exclusive) in O(log n).
reduce(int combine(int value, int element)) → int
Reduces a collection to a single value by iteratively combining elements of the collection using the provided function.
inherited
singleWhere(bool test(int element), {int orElse()?}) → int
The single element that satisfies test.
inherited
skip(int count) → Iterable<int>
Creates an Iterable that provides all but the first count elements.
inherited
skipWhile(bool test(int value)) → Iterable<int>
Creates an Iterable that skips leading elements while test is satisfied.
inherited
take(int count) → Iterable<int>
Creates a lazy iterable of the count first elements of this iterable.
inherited
takeWhile(bool test(int value)) → Iterable<int>
Creates a lazy iterable of the leading elements satisfying test.
inherited
toList({bool growable = true}) → List<int>
Converts the tree to a list in O(n).
override
toSet() → Set<int>
Creates a Set containing the same elements as this iterable.
inherited
toString() → String
Returns a string representation of (some of) the elements of this.
inherited
update(int index, int value) → void
Increments the element in the tree at index by value in O(log n).
where(bool test(int element)) → Iterable<int>
Creates a new lazy Iterable with all elements that satisfy the predicate test.
inherited
whereType<T>() → Iterable<T>
Creates a new lazy Iterable with all elements that have type T.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited
operator [](int index) → int
Returns the n-th element of this tree in O(log n).
operator []=(int index, int value) → void
Updates the n-th element of this tree in O(log n).