Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$. We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor_summatory_function and its approximation help us?Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast. Thanks!
Finding optimal set for a sum of a product function over a 2D lattice
lattices
The set $S$ must have the following form: there must exist a threshold $t$ such that:If $xy < t$, then $(x,y)$ is in $S$.Some or all of the points $(x,y)$ with $xy=t$ are in $S$.If $xy > t$, then $(x,y)$ is not in $S$.Moreover, in the second bullet, it doesn't matter which points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$.  Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.It follows that one way to parametrize the set is as$$S = \{(x,y) : xy < t \text{ or } (xy=t \text{ and } x<u)\},$$for some parameters $t,u$.  It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$.  How can we do that?One easy way is to use binary search.  Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy < t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy < t$, i.e., such that $y < t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$.  Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$.  This gives you the value of $t$.  It also gives you the number of points $(x,y)$ such that $xy<t$; call that number $k_0$.Once you know the value of $t$, the next step is to choose a suitable value for $u$.  We'll need to choose $u$ so that there are exactly $k-k_0$ lattice points $(x,y)$ such that $xy=t$ and $x<u$.  Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k_0$ of them.In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time.  The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.