C++ Reference: monoid_operation_tree

This documentation is automatically generated.



A monoid is an algebraic structure consisting of a set S with an associative binary operation * :S x S -> S that has an identity element. Associative means a*(b*c) = (a*b)*c for all a,b,c in S. An identity element is an element e in S such that for all a in S, e*a = a*e = a. See http://en.wikipedia.org/wiki/Monoid for more details.

A MonoidOperationTree is a data structure that maintains a product a_1 * a_2 * ... * a_n for a given (fixed) n, and that supports the following functions:
   - Setting the k-th operand to a given value in O(log n) calls to the * operation


   - Querying the result in O(1)

Note that the monoid is not required to be commutative.

The parameter class T represents an element of the set S. It must:
   * Have a public no-argument constructor producing the identity element.
   * Have a = operator method that sets its value to the given one.
   * Have a Compute(const T& left, const T& right) method that sets its value
   to the result of the binary operation for the two given operands.
   * Have a std::string DebugString() const method.

Possible use cases are:


   * Maintain a sum or a product of doubles, with a guarantee that the queried
   result is independent of the order of past numerical issues
   * Maintain a product of identically sized square matrices, which is an
   example of use with non-commutative operations.

Classes

MonoidOperationTree

Send feedback about...