B-tree_plus_alpha

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
• A dynamic wavelet matrix supporting range queries on a permutation (These queries can be used as range reporting queries on points over 2D space)

Download

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  

Compile

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.

Dynamic Data Structures

DynamicPrefixSum class

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.

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n log (M/n)) bits
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.

Example

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  
  
 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 class

DynamicBitSequence is a dynamic data structure supporting rank and select queries on a bit sequence.

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n) bits
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.

Example

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  
  
 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 class

DynamicSequence64 is a dynamic data structure that maintains a 64-bit non-negative sequence.

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n log (M/n)) bits
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.

Example

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  
 
 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 class

DynamicWaveletTree is a dynamic version of Wavelet Tree.

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n log σ) bits
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.

Example

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  
  
 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 class

DynamicPermutation is a dynamic data structure that maintains a permutation $S$ (a permutation of n integers 0, 1, ..., n-1).

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n log n) bits
Update Operation	S.insert(i, j)	amortized O(log n) time	Insert the (j+1)-th smallest value into S at position i
	S.erase(i)	amortized O(log n) time	Remove the (i+1)-th value from S
	S.move_pi_index(p, q)	amortized O(log n) time	Move the (p+1)-th value in S to the (q+1)-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

See this page for the member functions supported by DynamicPermutation.

Example

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 
  
 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]  

DynamicWaveletMatrixForRangeSearch class

DynamicWaveletMatrixForRangeSearch is a dynamic data structure that suuports range reporting query on a permutation $S$ (a permutation of n integers 0, 1, ..., n-1).

Table for update operations and queries

Category	Name	Order	Description
Memory		O(n log n) bits
Update Operation	S.insert($x_{rank}, y_{rank}$)	amortized O(log^{2} n) time	Insert the $(y_{rank}+1)$-th smallest value into $S$ at position $x_{rank}$
	S.erase_y_rank($y_{rank}$)	amortized O(log^{2} n) time	Remove the $(y_{rank}+1)$-th value from $S$
Query	S.range_report($x_{min}, x_{max}, y_{min}, y_{max}$, &out)	O((1 + occ) log^2 n) time	Report $occ$ elements in $S[x_{min}..x_{max}]$ such that each element $S[i]$ in $[y_{min}..y_{max}]$

See this page for the member functions supported by DynamicWaveletMatrixForRangeSearch.

Example

An example usage of DynamicPermutation is provided in dynamic_wavelet_matrix_for_range_search_example.cpp.
When this example is executed, the following message is displayed:

% ./dynamic_wavelet_matrix_for_range_search_example
  
Build DynamicWaveletMatrixForRangeSearch S from [8, 1, 5, 2, 6, 3, 7, 4, 0]
Print the integers stored in S
S = [8, 1, 3, 5, 7, 2, 4, 6, 0]
The number of elements in S is 9
S[0] = 8
The occurrence position of 3 in S is 5
The number of elements such that 1 <= S[i] <= 4 in S[0..3] is 2
Reported_indexes: [1, 2]
Insert 2 into S at position 1
S = [9, 2, 1, 4, 6, 8, 3, 5, 7, 0]
Delete an element $i$ such that $S[i] = 4$ from S
S = [8, 2, 1, 5, 7, 3, 4, 6, 0]
Write S to S.bin
Remove all values from S
S = []
Read S from S.bin
S = [8, 2, 1, 5, 7, 3, 4, 6, 0]

API Documentation (in preparation)

Doxygen