Before revision:  We develop a data structure with O( n log log n ) space,  O( log n + k ) query time, and expected O( n polylog n ) preprocessing time , removing a ( log^2 n log log n ) -factor from the O( n ( log^2 n )( log log n )^2 ) space of Bohler et al 's recent SoCG'16 work.
After revision:  We develop a data structure with O( n log log n ) space, O( log n + k ) query time, and expected O( n polylog n ) preprocessing time . The O( n log log n ) -factor from the O( n ( log^2 n )( log log n )^2 ) space of Bohler et al 's recent SoCG'16 work.