Allow me to join Sariel and Suresh and Adam and all the UIUC theory stduents in extoling Raimund Seidel and Micha Sharir's easy analysis of union-find with path compression. Go. Read. And remember, induction is your friend!

In his talk, Raimund described a similar (but simpler) analysis of space-time tradeoffs for partial-sum queries in the semigroup model, simplifying an old result of Chazelle. A semigroup is a set with an associative binary `addition' function, but not necessarily inverses or subtraction. Suppose we want to preprocess an array A[1..n] of elements of some semigroup (S,+), so that we can compute any partial sum A[i]+A[i+1]+...+A[j], given the indices i and j, using as few additions as possible (and no subtractions). If we don't allow any additions, the best we can do is store all n-choose-2 partial sums. If we allow exactly one addition, we only need to store O(n log n) partial sums. In general, if we allow at most 2k+1 additions per query, we only need to store O(n log^{*k} n) partial sums, where log^{*0} n = log n, log^{*k} 1 = 0 and log^{*k} n = 1 + log^{*k}(log^{*(k-1)} n). Finally, by storing only O(n) partial sums, we can answer a partial-sum query with only O(α(n)) additions, where α(n) is the smallest integer k such that log^{*k} n ≤ 2.

Raimund tells me their paper started with Micha saying "This is my favorite recurrence—it's solution is α(n)—but I don't know any way to use it!" So they tried applying it to path compression, and they succeeded. But then they simplified the argument even more, so Micha's recurrence wasn't necessary. Poor, poor recurrence. Nobody wants it.

## Comments