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

Question

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 2ドルN+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.

• Kaveh: 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: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5421
• Kaveh: 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.
• Chao Xu: Thanks, I have added some clarification. Didn't the paper say their main contribution is use 2ドルn+o(n)$ bits in both preprocessing and storage?
• Kaveh: 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).

Answer 1

You can save a lot more on memory if you just allow logarithmic time complexity. You can implement a kD segment tree that will need N * 2^k bits memory, and runs in logarithmic time complexity for both subtasks, and linear time complexity for building the tree.

If you strictly want O(1), precompute everything.

• Raphael: Can you outline how the tree is built in logarithmic time?
• Bojan Serafimov: sorry, its built in linear time
• Juho: @BojanSerafimov You should update the answer then :) Comments might be deleted.
• Raphael: I think this can be a good answer, if you just edited it to be correct and maybe a tad more elaborate on what these trees look like and how you build them.