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.