Discover the hidden algebraic structures in algorithms: monoids, semigroups, and how they power segment trees and parallel computation
Data structures aren't just containers — they have algebraic structure. One simple idea, the monoid, explains why folds run in parallel and why one segment tree works for many operations.
Pick a monoid, enter your own values if you like, and watch the fold combine them one step at a time. Try Sum, Max, GCD, and String: only the operation changes.
0+, 0Associative: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) | Identity: e ⊕ a = a ⊕ e = a
Current: [3, 1, 4, 1, 5, 9]
All these operations share the same structure: they have an identity element and are associative. This is why segment trees, parallel reduction, and prefix sums work with any monoid — not just addition!
The key concept is the monoid: a set with an associative operation and an identity element. This simple abstraction appears everywhere: segment trees, parallel reduction, prefix sums, and even distributed computing. Once you see it, you'll recognize it throughout computer science.
A monoid is a set with an associative binary operation and an identity element. Common examples: (numbers, +, 0), (numbers, max, -∞), (strings, concat, ""). Try different monoids and see how the fold operation works with each.
Choose a fold direction and step or play through it. Left, right, and parallel folds all reach the same answer, but the parallel fold needs only O(log n) depth.
Process elements from left to right: ((a ⊕ b) ⊕ c) ⊕ d
Because addition is associative, (a + b) + c = a + (b + c), all three fold directions give the same result. This is why we can parallelize! The parallel version can combine pairs simultaneously, reducing depth from O(n) to O(log n).
Associativity means we can group operations any way we want and get the same result. Watch how left-to-right folding, right-to-left folding, and parallel folding all compute the same answer — but parallel folding uses only O(log n) depth instead of O(n).
Set a left and right bound and press Show Query Path. Then switch the operation from Sum to Max to GCD: the tree and the path stay exactly the same.
The same segment tree structure works for ANY monoid. Only the combine operation changes!
The segment tree structure is monoid-agnostic. By swapping the monoid (Sum → Max → GCD), the exact same algorithm answers different queries. This is the power of algebraic abstraction!
A segment tree answers range queries in O(log n) time. The key insight: the same tree structure works for any monoid! Swap the operation from Sum to Max to GCD, and the algorithm remains identical. This is the power of algebraic abstraction.
Spot a mistake or have an idea?