Sum Tree

STSumTrees are faster than Sum Arrays for sampling, and they are easier to modify than Alias Tables. They're also capable of being modified quickly, so they're the preferred method for sampling without replacement.

Sum trees can be constructed in blueprint from sum arrays or weights.

Functions for sum trees are exposed to blueprint under the namespace 'Stoch.Utils.SumTree'.

note

Currently, Sum Trees are not editable in details views.

Uses

Grab Bags, Weighted Bags, and Nested Bags use sum trees internally.

Advanced

An STSumTree is a binary tree with each node corresponding to a sample-able item. Each node holds both its own value and the cumulative sum of all children. As a result, the root node contains the sum for the entire tree.

Precision

Precision is limited to 1 in 2^31, or about 1 in 2.1 billion.