Algorithm::BIT::XS - Binary indexed trees / Fenwick trees
use Algorithm::BIT::XS; my $bit = Algorithm::BIT::XS->new(100); $bit->update(1, 5); # bit[1] += 5 $bit->update(3, 6); # bit[3] += 6 say 'bit[1..2] == ', $bit->query(2); # 5 say 'bit[1..3] == ', $bit->query(3); # 11 say 'bit[1..20] == ', $bit->query(20); # 11 $bit->update(3, 10); # bit[3] += 10 say 'bit[1..3] == ', $bit->query(3); # 21 say 'bit[3] == ', $bit->get(3); # 16 $bit->set(3, 10); # bit[3] = 10 say 'bit[3] == ', $bit->get(3); # 10 $bit->clear; say 'bit[1..100] == ', $bit->query(100); # 0 $bit->set(100, 5); say 'bit[1..100] == ', $bit->query(100); # 5
A binary indexed tree is a data structure similar to an array of integers. The two main operations are updating an element and calculating a prefix sum, both of which run in time logarithmic in the size of the tree.
Create a new binary indexed tree of length $len. As binary indexed trees are 1-indexed, its indexes are [1..$len]. It is initially filled with zeroes.
Clears the binary indexed tree (sets all elements to 0).
Returns the prefix sum $bit[1] + $bit[2] + ... + $bit[$idx].
Adds $value to $bit[$idx].
Returns the value of $bit[$idx].
Sets $bit[$idx] to $value.
Algorithm::BIT, Algorithm::BIT2D::XS, https://en.wikipedia.org/wiki/Fenwick_tree
Marius Gavrilescu, <marius@ieval.ro>
Copyright (C) 2017 by Marius Gavrilescu
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.24.1 or, at your option, any later version of Perl 5 you may have available.
To install Algorithm::BIT::XS, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::BIT::XS
CPAN shell
perl -MCPAN -e shell install Algorithm::BIT::XS
For more information on module installation, please visit the detailed CPAN module installation guide.