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 $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.

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.