Segment Tree Generalization

Segment trees work for any associative operation with an identity element: | Operation | Merge | Identity | |-----------|-------|----------| | Sum | $a + b$ | $0$ | | Min | $\min(a, b)$ | $+\infty$ | | Max | $\max(a, b)$ | $-\infty$ | | Product | $a \cdot b$ | $1$ | | GCD | $\gcd(a, b)$ | $0$ | | XOR | $a \oplus b$ | $0$ | | AND | $a \land b$ | all 1s | | OR | $a \lor b$ | $0$ | The requirement: $(a \circ b) \circ c = a \circ (b \circ c)$ (associativity).

For non-associative operations (like median), segment trees don't directly work. You'd need to store more information at each node.