This repository implements the following five dynamic data structures using B-trees:
- A dynamic prefix-sum data structure for a sequence of non-negative integers
- A dynamic bit-vector supporting access, rank, and select queries
- A dynamic data structure supporting access queries on a sequence of non-negative integers
- A dynamic wavelet tree for strings
- A dynamic data structure supporting access queries on a permutation
The source code in the modules directory is maintained in separate repositories. To download all the required source code, follow the steps below:
git clone https://github.com/TNishimoto/b_tree_plus_alpha.git cd b_tree_plus_alpha git submodule init git submodule update B-tree_plus_alpha is a header-only library. To use this library, (i) include the include/all.hpp file, and (ii) add the modules directory to the include path. The examples directory contains a CMakeLists.txt file for compiling example programs.
DynamicPrefixSum is a dynamic prefix-sum data structure built on a sequence of non-negative integers. This class is implemented based on the technique described in Section 2.2 of this paper.
| Category | Name | Order | Description |
|---|---|---|---|
| Memory | O(n log (M/n)) bytes | ||
| Update Operation | S.insert(i, v) | amortized O(log n) time | Insert v into S as the i-th value |
| S.remove(i) | amortized O(log n) time | Remove the i-th value from S | |
| S.push_back(v) | amortized O(log n) time | Add v to S as the last value | |
| S.push_front(v) | amortized O(log n) time | Add v to S as the first value | |
| S.increment(i, v) | amortized O(log n) time | S[i] += v | |
| S.decrement(i, v) | amortized O(log n) time | S[i] -= v | |
| S.push_many(i, P) | amortized O(log n) time | Add the values in sequence P to S as the last values | |
| Query | S.psum(i) | O(log n) time | Return the sum of S[0..i] |
| S.search(v) | O(log n) time | Return the smallest index x that satisfies S.psum(x) >= v | |
| S.at(i) | O(log n) time | Return S[i] |
Here, S is a non-negative integer sequence stored in DynamicPrefixSum; n is the number of values in S; M is the sum of the values in S.
See this page for the member functions supported by DynamicPrefixSum.
An example usage of DynamicPrefixSum is provided in dynamic_prefix_sum_example.cpp. When this example is executed, the following message is displayed:
% ./dynamic_prefix_sum_example.out Build DynamicPrefixSum S from sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Print the values stored in S S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] The sum of S[0..3] is 10 Let x be the smallest index that satisfies psum(x) >= 10. Then, x = 3 Let y be the smallest index that satisfies psum(y) >= 1000. Then, y =-1 S[3] = 4 S[3] += 10 S[3] = 14 S[3] -= 10 S[3] = 4 Insert 100 into S at position 4 S = [1, 2, 3, 4, 100, 5, 6, 7, 8, 9, 10] Delete S[4] from S S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Add 0 to the tail of S Add 9 to the head of S S = [9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] Add 1, 2, 3, 4 to the tail of S S = [9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4] Write S to S.bin Remove all values from S S = [] Read S from S.bin S = [9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4] DynamicBitSequence is a dynamic data structure supporting rank and select queries on a bit sequence.
| Category | Name | Order | Description |
|---|---|---|---|
| Memory | O(n) bytes | ||
| Update Operation | S.insert(i, v) | amortized O(log n) time | Insert v into S as the i-th value |
| S.remove(i) | amortized O(log n) time | Remove the i-th value from S | |
| S.push_back(v) | amortized O(log n) time | Add v to S as the last value | |
| S.push_front(v) | amortized O(log n) time | Add v to S as the first value | |
| S.set_bit(i, v) | amortized O(log n) time | S[i] = v | |
| S.push_many(i, P) | amortized O(log n) time | Add the values in sequence P to S as the last values | |
| Query | S.psum(i) | O(log n) time | Return the sum of S[0..i] |
| S.search(v) | O(log n) time | Return the smallest index x that satisfies S.psum(x) >= v | |
| S.at(i) | O(log n) time | Return S[i] | |
| rank1(i) | O(log n) time | Return the number of 1 in S[0..i] | |
| rank0(i) | O(log n) time | Return the number of 0 in S[0..i] | |
| select1(i) | O(log n) time | Return the position of the (i+1)-th 1 in S | |
| select0(i) | O(log n) time | Return the position of the (i+1)-th 0 in S |
Here, S is a bit sequence stored in DynamicBitSequence; n is the number of values in S.
See this page for the member functions supported by DynamicBitSequence.
An example usage of DynamicBitSequence is provided in dynamic_bit_example.cpp. When this example is executed, the following message is displayed:
% ./dynamic_bit_example.out Build data structure S from bit sequence [1, 0, 1, 0, 1, 0, 1, 0, 1, 1] Print the bits stored in S S = [1010101011] The number of 1 in S[0..3] is 2 The number of 0 in S[0..3] is 2 The position of the third 1 in S is 4 The position of the third 0 in S is 5 The position of the fifth 0 in S is -1 Insert 1 into S at position 4 S = [10101101011] Delete S[4] from S S = [1010101011] Add 0 to the tail of S Add 1 to the head of S S = [110101010110] Add 1010 to the tail of S S = [1101010101101010] Write S to S.bin Remove all values from S S = [] Read S from S.bin S = [1101010101101010] DynamicSequence64 is a dynamic data structure that maintains a 64-bit non-negative sequence.
| Category | Name | Order | Description |
|---|---|---|---|
| Memory | O(n log (M/n)) bytes | ||
| Update Operation | S.insert(i, v) | amortized O(log n) time | Insert v into S as the i-th value |
| S.remove(i) | amortized O(log n) time | Remove the i-th value from S | |
| S.push_back(v) | amortized O(log n) time | Add v to S as the last value | |
| S.push_front(v) | amortized O(log n) time | Add v to S as the first value | |
| S.increment(i, v) | amortized O(log n) time | S[i] += v | |
| S.decrement(i, v) | amortized O(log n) time | S[i] -= v | |
| S.set_value(i, v) | amortized O(log n) time | S[i] = v | |
| S.push_many(i, P) | amortized O(log n) time | Add the values in sequence P to S as the last values | |
| Query | S.at(i) | O(log n) time | Return S[i] |
Here, S is a non-negative integer sequence stored in DynamicSequence64; n is the number of values in S; M is the sum of the values in S.
See this page for the member functions supported by DynamicSequence64.
An example usage of DynamicSequence64 is provided in dynamic_sequence_64_example.cpp.
When this example is executed, the following message is displayed:
./dynamic_sequence_64_example.out Build DynamicSequence64 S from integer sequence [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] Print the integers stored in S S = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] Insert 1 into S at position 4 S = [10, 20, 30, 40, 1, 50, 60, 70, 80, 90, 100] Delete S[4] from S S = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] Add 0 to the tail of S Add 1 to the head of S S = [1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 0] Add 1, 2, 3, 4 to the tail of S S = [1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 0, 1, 2, 3, 4] Write S to S.bin Remove all values from S S = [] Read S from S.bin S = [1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 0, 1, 2, 3, 4] DynamicWaveletTree is a dynamic version of Wavelet Tree.
| Category | Name | Order | Description |
|---|---|---|---|
| Memory | O(n log σ) bytes | ||
| Update Operation | S.insert(i, v) | amortized O(log σ log n) time | Insert v into S as the i-th character |
| S.remove(i) | amortized O(log σ log n) time | Remove the i-th character from S | |
| S.push_back(v) | amortized O(log σ log n) time | Add v to S as the last character | |
| S.push_many(i, P) | amortized O(log σ log n) time | Add the characters in sequence P to S as the last characters | |
| Query | S.at(i) | O(log σ log n) time | Return S[i] |
| S.rank(i, c) | O(log σ log n) time | Return the number of c in S[0..i] | |
| S.select(i, c) | O(log σ log n) time | Return the position of the (i+1)-th c in S |
Here, S is a string stored in DynamicWaveletTree; n is the length of S; σ is the the alphabet size of S.
See this page for the member functions supported by DynamicWaveletTree.
An example usage of DynamicWaveletTree is provided in dynamic_wavelet_tree_example.cpp.
When this example is executed, the following message is displayed:
% ./dynamic_wavelet_tree_example.out Print the integers stored in S S = ababababab The number of a in S[0..3] is 2 The number of b in S[0..3] is 2 The position of the third a in S is 4 The position of the third b in S is 5 The position of the 10-th b in S is -1 The position of the first c in S is -1 Insert c into S at position 4 S = ababcababab Delete S[4] from S S = ababababab Add c to the tail of S S = abababababc Add bbbb to the tail of S S = abababababcbbbb Write S to S.bin Remove all values from S S = Read S from S.bin S = abababababcbbbb DynamicPermutation is a dynamic data structure that maintains a permutation.
| Category | Name | Order | Description |
|---|---|---|---|
| Memory | O(n log n) bytes | ||
| Update Operation | S.insert(i, j) | amortized O(log n) time | Insert the j-th smallest value into S at position i |
| S.erase(i) | amortized O(log n) time | Remove the i-th value from S | |
| S.move_pi_index(p, q) | amortized O(log n) time | Move the p-th value in S to the q-th value | |
| Query | S.access(i) | O(log n) time | Return S[i] |
| S.inverse(i) | O(log n) time | Return the index j that satisfies S[j] = i |
Here, S is a permutation of n integers 0, 1, ..., n-1 stored in DynamicPermutation.
See this page for the member functions supported by DynamicPermutation.
An example usage of DynamicPermutation is provided in dynamic_permutation_example.cpp.
When this example is executed, the following message is displayed:
% ./dynamic_permutation_example.out Build DynamicPermutation S from permutation [0, 3, 1, 2, 5, 4, 9, 8, 7, 6] Constructing Dynamic Permutation... (input size = 10) Processing... [0KB] [END], the number of nodes = 1, Elapsed Time: 0 sec (0 ms/MB) Print the integers stored in S S = [0, 3, 1, 2, 5, 4, 9, 8, 7, 6] S[3] = 2 S^{-1}[3] = 1 Insert 2 into S at position 1 S = [0, 2, 4, 1, 3, 6, 5, 10, 9, 8, 7] Delete S[4] from S S = [0, 2, 3, 1, 5, 4, 9, 8, 7, 6] Move S[1] in S to position 0 S = [2, 0, 3, 1, 5, 4, 9, 8, 7, 6] Write S to S.bin Remove all values from S S = [] Read S from S.bin S = [2, 0, 3, 1, 5, 4, 9, 8, 7, 6]