[kele]

The union-find data structure (the idea is so simple and a sophisticated analysis yields a really low upper bound).

RMQ with linear preprocessing and constant time queries (which is also true for multi-dimensional cases, if the dimension is bounded by a constant).

Knuth-Morris-Pratt pattern matching is the first algorithm where I saw the usage of an additional variable in the pseudocode just to simplify the complexity analysis.