Showing that interval-sum queries on a binary array can not be done using linear space and constant time 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.
I wouldn’t be so sure such an algorithm doesn’t exist; there are certainly algorithms that get very close. Below, $\log n$ is $\log_2n$, $\log^{(k)}n$ is $\mathop{\underbrace{\log\dots\log}_{k\text{ times}}}n$, $\log^*n$ is iterated logarithm, and $\tilde O(t(n))$ is $O(t(n)\operatorname{polylog}(t(n)))$.


  Proposition: There are algorithms that achieve
  
  
  space $O(n\log^{(k)}n)$ and query time $O(1)$ for any constant $k$;
  space $O(n)$ and query time $\tilde O(\log^*n)$.
  


The algorithms work as follows. There are parameters $k&gt;0$ and $n=b_0&gt;b_1&gt;\dots&gt;b_k&gt;0$ depending on $n$. We split the input size-$b_0$ array into size-$b_1$ blocks (level 1); we split each level-1 block into size $b_2$ blocks (level 2); and so on up to level $k$. (Let us pretend all $b_i$ are powers of $2$, to avoid issues with divisibility.) Then:


For each $i=1,\dots,k$ and each level-$i$ block, we store the number of set bits in the interval from the beginning of the block down to the nearest level-$(i-1)$ block boundary.
In order to resolve a query, we sum the $k$ stored numbers corresponding to the index, and count the set bits before the index in its level-$k$ block. We do all this for $x$ and $y$ separately, and subtract the results.


(If the $b_i$ parameters are not easy to compute, we might also store them.)

This arrangement uses space
$$n\sum_{i=1}^k\frac{\log b_{i-1}}{b_i},$$
and query time
$$O(k+b_k).$$

In the proposition, for 1., we let $k$ be constant, and put $b_i=\log^{(i)}n$ for $0&lt;i&lt;k$, $b_k=1$.

For 2., we can take $k=\log^*n$, and
$$b_i=i(\log i)^3\log^{(i)}n.$$
The space is then bounded by roughly
$$n\sum_{i=1}^k\frac{\log^{(i)}n+2\log i}{i(\log i)^3\log^{(i)}n}\le
n\sum_{i=1}^\infty\frac{3}{i(\log i)^2}=cn$$
for some constant $c$.