NAME

Algorithm::BIT2D::XS - 2D Binary indexed trees / Fenwick trees

SYNOPSIS

  use Algorithm::BIT2D::XS;
  my $bit = Algorithm::BIT2D::XS->new(100, 100);
  $bit->update(1, 2, 5);  # bit[1][2] += 5
  $bit->update(3, 3, 6);  # bit[3][3] += 6
  say 'bit[1..2][1..10]  == ', $bit->query(2, 10);  # 5
  say 'bit[1..3][1..2]   == ', $bit->query(3, 2);  # 5
  say 'bit[1..20][1..10] == ', $bit->query(20, 10); # 11

  $bit->update(3, 1, 10); # bit[3][1] += 10
  say 'bit[1..3][1..3]  == ', $bit->query(3, 3);  # 21
  say 'bit[3][3] == ', $bit->get(3, 3); # 6

  $bit->set(3, 3, 10); # bit[3][3] = 10
  say 'bit[3][3] == ', $bit->get(3, 3); # 10

  $bit->clear;
  say 'bit[1..100][1..10] == ', $bit->query(100, 10); # 0
  $bit->set(100, 10, 5);
  say 'bit[1..100][1..10] == ', $bit->query(100, 10); # 5

DESCRIPTION

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.

Algorithm::BIT2D::XS->new($n, $m)

Create a new 2D binary indexed tree of length $n x $m. As binary indexed trees are 1-indexed, its indexes are [1..$n][1..$m]. It is initially filled with zeroes.

$bit->clear()

Clears the binary indexed tree (sets all elements to 0).

$bit->query($i1, $i2)

Returns the rectangle sum from $bit[1][1] to $bit[$i1][$i2].

$bit->update($i1, $i2, $value)

Adds $value to $bit[$i1][$i2].

$bit->get($i1, $i2)

Returns the value of $bit[$i1][$i2].

$bit->set($i1, $i2, $value)

Sets $bit[$i1][$i2] to $value.

SEE ALSO

Algorithm::BIT, Algorithm::BIT::XS, https://en.wikipedia.org/wiki/Fenwick_tree

AUTHOR

Marius Gavrilescu, <marius@ieval.ro>

COPYRIGHT AND LICENSE

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.