lib/Algorithm/BIT2D/XS.pm

   1 package Algorithm::BIT2D::XS;
   2
   3 use 5.014000;
   4 use strict;
   5 use warnings;
   6
   7 our $VERSION = '0.001';
   8
   9 use Algorithm::BIT::XS;
  10
  11 sub new {
  12         my ($class, $n, $m) = @_;
  13         create($n, $m);
  14 }
  15
  16 sub get {
  17         my ($b, $i1, $i2) = @_;
  18         $b->query($i1, $i2) + $b->query($i1 - 1, $i2 - 1)
  19           - $b->query($i1 - 1, $i2) - $b->query($i1, $i2 - 1);
  20 }
  21
  22 sub set {
  23         my ($b, $i1, $i2, $value) = @_;
  24         $b->update($i1, $i2, $value - $b->get($i1, $i2))
  25 }
  26
  27 1;
  28 __END__
  29
  30 =encoding utf-8
  31
  32 =head1 NAME
  33
  34 Algorithm::BIT2D::XS - 2D Binary indexed trees / Fenwick trees
  35
  36 =head1 SYNOPSIS
  37
  38   use Algorithm::BIT2D::XS;
  39   my $bit = Algorithm::BIT2D::XS->new(100, 100);
  40   $bit->update(1, 2, 5);  # bit[1][2] += 5
  41   $bit->update(3, 3, 6);  # bit[3][3] += 6
  42   say 'bit[1..2][1..10]  == ', $bit->query(2, 10);  # 5
  43   say 'bit[1..3][1..2]   == ', $bit->query(3, 2);  # 5
  44   say 'bit[1..20][1..10] == ', $bit->query(20, 10); # 11
  45
  46   $bit->update(3, 1, 10); # bit[3][1] += 10
  47   say 'bit[1..3][1..3]  == ', $bit->query(3, 3);  # 21
  48   say 'bit[3][3] == ', $bit->get(3, 3); # 6
  49
  50   $bit->set(3, 3, 10); # bit[3][3] = 10
  51   say 'bit[3][3] == ', $bit->get(3, 3); # 10
  52
  53   $bit->clear;
  54   say 'bit[1..100][1..10] == ', $bit->query(100, 10); # 0
  55   $bit->set(100, 10, 5);
  56   say 'bit[1..100][1..10] == ', $bit->query(100, 10); # 5
  57
  58 =head1 DESCRIPTION
  59
  60 A binary indexed tree is a data structure similar to an array of integers.
  61 The two main operations are updating an element and calculating a
  62 prefix sum, both of which run in time logarithmic in the size of the tree.
  63
  64 =over
  65
  66 =item Algorithm::BIT2D::XS->B<new>(I<$n>, I<$m>)
  67
  68 Create a new 2D binary indexed tree of length I<$n> x I<$m>. As binary
  69 indexed trees are 1-indexed, its indexes are [1..I<$n>][1..I<$m>].
  70 It is initially filled with zeroes.
  71
  72 =item $bit->B<clear>()
  73
  74 Clears the binary indexed tree (sets all elements to 0).
  75
  76 =item $bit->B<query>(I<$i1>, I<$i2>)
  77
  78 Returns the rectangle sum from I<$bit>[1][1] to I<$bit>[I<$i1>][I<$i2>].
  79
  80 =item $bit->B<update>(I<$i1>, I<$i2>, I<$value>)
  81
  82 Adds I<$value> to I<$bit>[I<$i1>][I<$i2>].
  83
  84 =item $bit->B<get>(I<$i1>, I<$i2>)
  85
  86 Returns the value of I<$bit>[I<$i1>][I<$i2>].
  87
  88 =item $bit->B<set>(I<$i1>, I<$i2>, I<$value>)
  89
  90 Sets I<$bit>[I<$i1>][I<$i2>] to I<$value>.
  91
  92 =back
  93
  94 =head1 SEE ALSO
  95
  96 L<Algorithm::BIT>, L<Algorithm::BIT::XS>, L<https://en.wikipedia.org/wiki/Fenwick_tree>
  97
  98 =head1 AUTHOR
  99
 100 Marius Gavrilescu, E<lt>marius@ieval.roE<gt>
 101
 102 =head1 COPYRIGHT AND LICENSE
 103
 104 Copyright (C) 2017 by Marius Gavrilescu
 105
 106 This library is free software; you can redistribute it and/or modify
 107 it under the same terms as Perl itself, either Perl version 5.24.1 or,
 108 at your option, any later version of Perl 5 you may have available.
 109
 110
 111 =cut