# Bit complexity of O(1) time range query in a $k$-ary array

Consider the following problem:

Let $k$ be a constant. We are given a $k$-ary array $A_{d_1\times\ldots\times d_k}$ of $0$ and $1$'s. Let $N = \prod_{i=1}^k d_i$.

We want to create a data structure by preprocessing $A$ to perform the following type of query operations:

1. Given the coordinates of a $k$-ary box $D$, is there a $1$ in the box?
2. Given the coordinates of a $k$-ary box $D$, return the position of a $1$ in the box (if there is one).

The operations must be performed in constant time $O(1)$. The time complexity is measured on a RAM machine. The preprocessing time and space for the data structure are not important for us.

The question is how much space (in bit complexity) do we need to store a datastructure allowing the above operations?

The trivial lower-bound is $N$ bits since the array can be reconstructed for these queries (so the data structure should have at least the same amount of information in it).

The trivial upper-bound is to store the answer to all of the queries. That would need $\prod_{i=1}^k {d_i \choose 2} = \Theta(N^2)$ bits. However we suspect that this can be done much more efficiently.

For example, consider the special case where $k=1$. In this case we can use a succinct RMQ data structure to solve the first problem, and the data structure takes $2N+o(N)$ bits to store.

What is an efficient data-structure for this task?
How low can the space complexity (the number of bits) go to support these operations (or just the first operation)?

Update (1/15): In the special case $k=1$, using $N +o(N)$ bits is sufficient (actually better, $\log {N\choose t}+O(t)$, where $t$ is the number of $1$'s in $A$) by reducing the problem to a predecessor problem and using the reduction from predecessor problem to fully indexable dictionary (FID). See "More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries" by Grossi, Orlandi, Raman and Rao (2009).

Update (6/27): Again by reduce the problem to RMQ. We use a $k$-dimensional RMQ by Yuan and Atallah to get a $O(n\log n)$ upper bound on the amount of space required when $k$ is fixed.

• The question is not clear: is this a data-structure question? If so what are the other operations on this kD array? If there is no other operation then there is no 1 on it. If the question is that we are given a kD array and what to do some preprocessing on it and then store it such that we use little amount of memory but can perform this checking operation in $O(1)$ worst-case then clarify that. Also explain what is the model of computation if you want a lower bound. – Kaveh Jan 13 '13 at 17:36
• citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5421 – Kaveh Jan 13 '13 at 18:05
• IIUC, the paper says the answer for 1D is really $O(n\lg n)$ bits and the idea is to store all small boxes plus all boxes with lengths of power 2 and other boxes can be obtained from len pow-2 boxes in constant time ($O(2^k)$) and it seems to me that the same thing would work here and $O(n^k\lg^k n)$ bits will be sufficient. – Kaveh Jan 13 '13 at 18:31
• Thanks, I have added some clarification. Didn't the paper say their main contribution is use $2n+o(n)$ bits in both preprocessing and storage? – Chao Xu Jan 13 '13 at 20:58
• Sorry, the one I described was from previous work. However their result seems to be conceptually similar, i.e. they divide the array to blocks, precompute the answer on them, and use a constant number of them to compute the answer for any given one. If in kD the number of base blocks that one needs to compute the answer to an arbitrary block is a constant then a similar algorithm would work here and would give probably something like $O(n^k) = O(N)$ (I haven't check that this is the case). – Kaveh Jan 14 '13 at 6:44