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:


Given the coordinates of a $k$-ary box $D$, is there a $1$ in the box?  
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.
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.