Before revision:  That is, can we get an improved amortized per-sample cost if we allow a more costly preprocessing phase?
After revision:  That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase?