Binary Indexed Tree a.k.a Fenwick Tree
Perl
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lib/Algorithm
t
Changes
MANIFEST
Makefile.PL
README

README

NAME
    Algorithm::BIT - Binary Indexed Tree a.k.a Fenwick Tree

SYNOPSIS
      use Algorithm::BIT;

      my $bit = Algorithm::BIT->new(16); # 16 is a numbers of objects

      ## updating frequencies in O(lg n)
      $bit->update(1, 2); # object#1 occuring 2 times
      $bit->update(5, 1);
      $bit->update(8, 2);

      ## getting cumulative frequencies in O(lg n)
      say $bit->read(1);  # 2
      say $bit->read(2);  # 2
      say $bit->read(5);  # 3
      say $bit->read(10); # 5

DESCRIPTION
    Binary Indexed Tree (BIT) is able to compute cumulative sum of any range
    of consecutive elements in O(lg n) and also changing value of any single
    element needs O(lg n) time as well.(quote from
    http://www.algorithmist.com/index.php/Fenwick_tree)

SEE ALSO
    http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTr
    ees

AUTHOR
    Naoya Ito, <naoya at bloghackers.net<gt>

COPYRIGHT AND LICENSE
    This library is free software; you can redistribute it and/or modify it
    under the same terms as Perl itself, either Perl version 5.8.8 or, at
    your option, any later version of Perl 5 you may have available.