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.