class

Crystalg::DataStructures::FenwickTree(T)

Inherits Reference < Object

Fenwick Tree can efficiently update elements and calculate prefix sums in a table of numbers. Type argument T must be the Group.

fenwick = FenwickTree(Int32).new(5)

fenwick[0] = 1
fenwick[1] = 3
fenwick[2] = 5
fenwick[3] = 7
fenwick[4] = 11

# sum method returns sum of [0, index). If given index is 0, returns 0.
fenwick.sum(0) # => 0
fenwick.sum(3) # => 9
fenwick.sum(5) # => 27

Constructors

new(size : Int32)

Creates FenwickTree(T).

Source

Instance methods

[]=(index : Int, value : T)

Sets the given value at the given index. O(log n).

Source

sum(index : Int)

Adds elements that index less than or equeals key in the collection together. O(log n).

Source