Sum Trees

This module implements a class to hold a Sum Tree, an object similar to a Haar Wavelet tree, with the difference that each node encodes the plain sum of the children's coefficients. This data-structure allows O(log(N)) modifications to the values associated with the leaves of the tree.

An example usage of this class is to sample CDFs that are continuously updated over time.

This data structure is storage-free and relies on the user to provide the combined storage for the leaves and the internal nodes using a template iterator. It can be used both in host and device code.

See:

• SumTree
• uint32 sample<Iterator>(const SumTree<Iterator>& tree, const float value)

Example

// build a PDF, assigning each slot a value between 0 and 10.
// NOTE: we need to alloc space for the leaves as well as the inner nodes.
const uint32 n_leaves = 100;
const uint32 n_nodes  = SumTree<uint32*>::node_count( n_leaves );
std::vector<float> probs( n_nodes );
for (uint32 i = 0; i < n_leaves; ++i)
    probs[i] = uint32( drand48() * 10 );

// build the sum tree
SumTree<float*> prob_tree( n_leaves, &probs[0] );
prob_tree.setup();

// pick its cells in random order with probability proportional to their value,
// and every time a cell is sampled decrease its probability by 1.
while (prob_tree.sum() > 0)
{
    // sample a cell using our probability tree
    const uint32 cell = sample( prob_tree, drand48() );

    // decrease by one this cell's probability
    prob_tree.add( cell, -1 );

    // and do something with the selected cell...
    record_event( cell );
}