You are given a $n$-sized binary array.
I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):
1) Pre-process the input array using unlimited time, but only using $O(n)$ bits.
2) Answer queries in constant time, where query $(x,y)$ asks for the number of set bits between index $x$ and index $y$ in the array.
It seems that constant time per query should not allow the algorithm to read enough information to compute the number of set bits.
How can we prove that no such algorithm exists?
A more general question would be,
given that the algorithm is allowed to use $f(n)$ space, what lower bound on the query time can we derive?
Obviously, if we have $f=\Omega(n\log n)$ space we can store the all partial sums and answer queries in $O(1)$, but what if $f$ is smaller?
You may assume that the size of a memory word is $\Theta(\log n)$ and we can read the $x,y$ indices in constant time.