]>
iEval git - algorithm-bit-xs.git/blob - XS.pm
e0b6afd0c89cf94907294966e2a303dacb565745
1 package Algorithm
::BIT2D
::XS
;
7 our $VERSION = '0.003';
9 use Algorithm
::BIT
::XS
;
12 my ($class, $n, $m) = @_;
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);
23 my ($b, $i1, $i2, $value) = @_;
24 $b->update($i1, $i2, $value - $b->get($i1, $i2))
34 Algorithm::BIT2D::XS - 2D Binary indexed trees / Fenwick trees
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
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
50 $bit->set(3, 3, 10); # bit[3][3] = 10
51 say 'bit[3][3] == ', $bit->get(3, 3); # 10
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
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.
66 =item Algorithm::BIT2D::XS->B<new>(I<$n>, I<$m>)
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.
72 =item $bit->B<clear>()
74 Clears the binary indexed tree (sets all elements to 0).
76 =item $bit->B<query>(I<$i1>, I<$i2>)
78 Returns the rectangle sum from I<$bit>[1][1] to I<$bit>[I<$i1>][I<$i2>].
80 =item $bit->B<update>(I<$i1>, I<$i2>, I<$value>)
82 Adds I<$value> to I<$bit>[I<$i1>][I<$i2>].
84 =item $bit->B<get>(I<$i1>, I<$i2>)
86 Returns the value of I<$bit>[I<$i1>][I<$i2>].
88 =item $bit->B<set>(I<$i1>, I<$i2>, I<$value>)
90 Sets I<$bit>[I<$i1>][I<$i2>] to I<$value>.
96 L<Algorithm::BIT>, L<Algorithm::BIT::XS>, L<https://en.wikipedia.org/wiki/Fenwick_tree>
100 Marius Gavrilescu, E<lt>marius@ieval.roE<gt>
102 =head1 COPYRIGHT AND LICENSE
104 Copyright (C) 2017 by Marius Gavrilescu
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.
This page took 0.053463 seconds and 3 git commands to generate.