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 near-linear space and optimal query time of O(m+k) , and our second result achieves linear space and near optimal query time .