Before revision:    Our first result achieves near-linear space and optimal query time  , and our second result achieves linear space and near optimal query time .
After revision:  Our first result achieves O(n\log n) space and optimal query time , and our second result achieves linear space and near optimal query time .