# 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$$ is a timestamp and $$b_i$$ is an arbitrary real. 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 timestamp $$q$$ 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 $$(q-1, q)$$.

Note: The $$a_i$$'s are not necessarily in sorted order in the stream. There are no additional assumptions about the the distribution of the timestamps or the values $$b_i$$. While I am looking for a solution with worst-case time complexity for both methods, I would also be interested in seeing if the data structure could be achieved in amortized time complexity for each or both methods.

• What approaches have you considered? What's the context where you encountered this problem? Do you have any particular reason to think a solution exists? Would you be satisfied with logarithmic-time insert? $O(1)$ time insertions is quite a restrictive condition. – D.W. Nov 16 '20 at 7:55
• Operation 2 needs to be sublinear in terms of what? – orlp Nov 16 '20 at 16:18
• @D.W. My friend was asked this in an interview, and we couldn't figure it out afterwards. I was thinking to somehow use a segment tree, but the issue with any tree approach is $\mathcal{O}(\log n)$ insertion. – EulerMacaroni Nov 16 '20 at 17:46
• @orlp sublinear in terms of the number of elements of the stream already added to the data structure. – EulerMacaroni Nov 16 '20 at 17:46
• Do we have to assume worst-case inputs or can we make some assumptions, like that the inputs are uniformly randomly distributed, or that that are random and iid from some unknown distribution? Would you be OK with an amortized running time? – D.W. Nov 16 '20 at 18:18

## 1 Answer

If they're timestamps, there's a good chance they are approximately randomly distributed across some range, say $$[\ell,u]$$. In this case there exist reasonable solution.

You can hash each pair into $$k$$ equal-width buckets in this range, i.e., using the hash function $$h(a,b) = \lfloor N(a-\ell)/(u-\ell) \rfloor$$, where $$k$$ is roughly similar to the number of items seen so far. Within a bucket, remember the largest value of $$b$$ of all pairs that hashed into that bucket. Then insert can be done in $$O(1)$$ expected time, and lookup can be done in $$O(1)$$ expected time.

Of course, we won't know $$[\ell,u]$$ exactly, and $$\ell,u,k$$ will change over time. However you can adjust on the fly, by keeping track of the smallest and largest timestamp seen and the number of pairs seen so far. Every time the number of pairs doubles, you update the hash function and rehash. Naively, that sounds like it takes $$O(n)$$ time to rehash, but you can spread that out over the next $$n/4$$ inserts, maintaining the $$O(1)$$ expected running time.

If the timestamps aren't uniformly distributed but they come iid from some distribution, and the distribution is "smooth" enough, then I think you can find a similar solution. Keep track of the integer-percentiles of the $$a$$ values (i.e., the 0% percentile value, the 1% percentile value, the 2% percentile value, and so on); it is possible to estimate these values using streaming quantile estimation / streaming histogram estimation. To hash a pair, convert its $$a$$ value to a percentile (a real number $$p$$ in the range $$[0,1]$$), using linear interpolation among these 101 known percentile values; then $$p$$ will be approximately uniformly distributed on $$[0,1]$$, and you can hash $$p$$ into equal-width buckets as before. If the distribution is smooth enough, linear interpolation will work well and $$p$$ will be approximately uniformly distributed. If the distribution is not smooth, this may work poorly.

• If the range is limited, you could also use y-fast trees. – Pseudonym Nov 18 '20 at 3:28