Commit | Line | Data |
---|---|---|
0c7cf8e9 MG |
1 | package Algorithm::BIT2D::XS; |
2 | ||
3 | use 5.014000; | |
4 | use strict; | |
5 | use warnings; | |
6 | ||
34876640 | 7 | our $VERSION = '0.002'; |
0c7cf8e9 MG |
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 |