Before revision:  Constructing the data structure requires  O(\frac{q{\varepsilon^2}} {\varepsilon^2}} ) samples for general Gibbs distributions and  O(\frac{n^2{\varepsilon^2}} {\varepsilon^2} + n \log q} ) samples for integer-valued distributions.
After revision:  Constructing the data structure requires  O(\frac{q{\varepsilon^2}} O(\frac{q \log n{\varepsilon^2}} ) samples for general Gibbs distributions and  O(\frac{n^2{\varepsilon^2}} {\varepsilon^2} + n \log q} ) samples for integer-valued distributions.