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

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.