mlpack 3.4.2
|
Implementation of SumTree. More...
#include <sumtree.hpp>
Public Member Functions | |
SumTree () | |
Default constructor. More... | |
SumTree (const size_t capacity) | |
Construct an instance of SumTree class. More... | |
void | BatchUpdate (const arma::ucolvec &indices, const arma::Col< T > &data) |
Update the data with batch rather loop over the indices with set method. More... | |
size_t | FindPrefixSum (T mass) |
Find the highest index idx in the array such that sum(arr[0] + arr[1] + ... + arr[idx]) <= mass. More... | |
T | Get (size_t idx) |
Get the data array with idx. More... | |
void | Set (size_t idx, const T value) |
Set the data array with idx. More... | |
T | Sum () |
Shortcut for calculating the sum of whole array. More... | |
T | Sum (const size_t start, size_t end) |
Calculate the sum of contiguous subsequence of the array. More... | |
T | SumHelper (const size_t start, const size_t end, const size_t node, const size_t nodeStart, const size_t nodeEnd) |
Help function for the sum function. More... | |
Implementation of SumTree.
Build a Segment Tree like data structure. https://en.wikipedia.org/wiki/Segment_tree
Used to maintain prefix-sum of an array.
T | The array's element type. |
Definition at line 32 of file sumtree.hpp.
|
inline |
Default constructor.
Definition at line 38 of file sumtree.hpp.
|
inline |
Construct an instance of SumTree class.
capacity | Size of data. |
Definition at line 46 of file sumtree.hpp.
|
inline |
Update the data with batch rather loop over the indices with set method.
indices | The indices of data to be changed. |
data | The data that array with indices to be. |
Definition at line 75 of file sumtree.hpp.
|
inline |
Find the highest index idx
in the array such that sum(arr[0] + arr[1] + ... + arr[idx]) <= mass.
mass | The upper bound of segment array sum. |
Definition at line 163 of file sumtree.hpp.
|
inline |
Get the data array with idx.
idx | The array idx to get data. |
Definition at line 93 of file sumtree.hpp.
|
inline |
Set the data array with idx.
idx | The array idx to be changed. |
value | The data that array with idx to be. |
Definition at line 57 of file sumtree.hpp.
|
inline |
Shortcut for calculating the sum of whole array.
Definition at line 152 of file sumtree.hpp.
References SumTree< T >::Sum().
Referenced by SumTree< T >::Sum().
|
inline |
Calculate the sum of contiguous subsequence of the array.
start | The starting position of subsequence. |
end | The end position of subsequence. |
Definition at line 143 of file sumtree.hpp.
References SumTree< T >::SumHelper().
|
inline |
Help function for the sum
function.
start | The starting position of subsequence. |
end | The end position of subsequence. |
node | Reference position. |
nodeStart | Starting position of reference segment. |
nodeEnd | End position of reference segment. |
Definition at line 108 of file sumtree.hpp.
References SumTree< T >::SumHelper().
Referenced by SumTree< T >::Sum(), and SumTree< T >::SumHelper().