class Crystalg::DataStructures::FenwickTree(T)

Overview

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

Defined in:

crystalg/data_structures/fenwick_tree.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(size : Int32) #

Creates FenwickTree(T).


[View source]

Instance Method Detail

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

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


[View source]
def sum(index : Int) #

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


[View source]