The existing work [1]}, [2]} implies the following result. However their proofs are very decent and complicated. We provide another data structure in Section  that significantly simplifies the analysis (by only paying some extra log factors). We believe it is of independent interest.
