A. Andersson, P.B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions.
Theoretical Computer Science, vol 215, pp 337-344, 1999.

Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC^o instructions only. More precisely, we show that a subset of {0,...,2^(w-1)} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O(log n/loglog n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are fuinctions in AC^0. The AC^0 instructions used are not all available on today's computers.

Full paper (postscript)
Full paper (pdf)