We present an efficient algorithm to approximate the Automatic Color Equalization (ACE) of an input color image, with an upper-bound on the introduced approximation error. The computation is based on Summed Area Tables and a carefully optimized partitioning of the plane into rectangular regions, resulting in a pseudo-linear asymptotic complexity with the number of pixels (against a quadratic straightforward computation of ACE). Our experimental evaluation confirms both the speedups and high accuracy, reaching lower approximation errors than existing approaches. We provide a publicly available reference implementation of our algorithm.