]>
Commit | Line | Data |
---|---|---|
1 | package Algorithm::BIT::XS; | |
2 | ||
3 | use 5.014000; | |
4 | use strict; | |
5 | use warnings; | |
6 | ||
7 | our $VERSION = '0.002'; | |
8 | ||
9 | require XSLoader; | |
10 | XSLoader::load('Algorithm::BIT::XS', $VERSION); | |
11 | ||
12 | sub new { | |
13 | my ($class, $len) = @_; | |
14 | create($len); | |
15 | } | |
16 | ||
17 | sub get { | |
18 | my ($b, $idx) = @_; | |
19 | $b->query($idx) - $b->query($idx - 1); | |
20 | } | |
21 | ||
22 | sub set { | |
23 | my ($b, $idx, $value) = @_; | |
24 | $b->update($idx, $value - $b->get($idx)) | |
25 | } | |
26 | ||
27 | 1; | |
28 | __END__ | |
29 | ||
30 | =encoding utf-8 | |
31 | ||
32 | =head1 NAME | |
33 | ||
34 | Algorithm::BIT::XS - Binary indexed trees / Fenwick trees | |
35 | ||
36 | =head1 SYNOPSIS | |
37 | ||
38 | use Algorithm::BIT::XS; | |
39 | my $bit = Algorithm::BIT::XS->new(100); | |
40 | $bit->update(1, 5); # bit[1] += 5 | |
41 | $bit->update(3, 6); # bit[3] += 6 | |
42 | say 'bit[1..2] == ', $bit->query(2); # 5 | |
43 | say 'bit[1..3] == ', $bit->query(3); # 11 | |
44 | say 'bit[1..20] == ', $bit->query(20); # 11 | |
45 | ||
46 | $bit->update(3, 10); # bit[3] += 10 | |
47 | say 'bit[1..3] == ', $bit->query(3); # 21 | |
48 | say 'bit[3] == ', $bit->get(3); # 16 | |
49 | ||
50 | $bit->set(3, 10); # bit[3] = 10 | |
51 | say 'bit[3] == ', $bit->get(3); # 10 | |
52 | ||
53 | $bit->clear; | |
54 | say 'bit[1..100] == ', $bit->query(100); # 0 | |
55 | $bit->set(100, 5); | |
56 | say 'bit[1..100] == ', $bit->query(100); # 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::BIT::XS->B<new>(I<$len>) | |
67 | ||
68 | Create a new binary indexed tree of length I<$len>. As binary indexed | |
69 | trees are 1-indexed, its indexes are [1..I<$len>]. It is initially | |
70 | 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<$idx>) | |
77 | ||
78 | Returns the prefix sum I<$bit>[1] + I<$bit>[2] + ... + I<$bit>[I<$idx>]. | |
79 | ||
80 | =item $bit->B<update>(I<$idx>, I<$value>) | |
81 | ||
82 | Adds I<$value> to I<$bit>[I<$idx>]. | |
83 | ||
84 | =item $bit->B<get>(I<$idx>) | |
85 | ||
86 | Returns the value of I<$bit>[I<$idx>]. | |
87 | ||
88 | =item $bit->B<set>(I<$idx>, I<$value>) | |
89 | ||
90 | Sets I<$bit>[I<$idx>] to I<$value>. | |
91 | ||
92 | =back | |
93 | ||
94 | =head1 SEE ALSO | |
95 | ||
96 | L<Algorithm::BIT>, L<Algorithm::BIT2D::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 |