# algorithms – Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $$i^{text{th}}$$ element in the stream is an ordered pair $$(a_i, b_i)$$, where $$a_i$$ and $$b_i$$ are both arbitrary reals. How can we design a data structure with the following two methods:

1. $$mathcal{O}(1)$$ insert
2. Sublinear lookup to determine when, given some real $$a$$ as an argument, find the maximum value of $$b_i$$ for all elements $$(a_i, b_i)$$ already in our data structure with $$a_i$$ in the range $$(a-1, a)$$.

Note: The $$a_i$$‘s are not necessarily in sorted order in the stream.