Before revision:  We show that  the approximation factor achieved by our data structure is optimal in the cell-probe model of computation.
After revision:  We show that under some conditions the approximation factor achieved by our data structure is optimal in the cell-probe model of computation.