Showing that interval-sum queries on a binary array can not be done using linear space and 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$.