 Theoretical Computer Science

# 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. ## Solution

I believe that what you are looking for is a compact data structure supporting the rank operation. See...

https://en.m.wikipedia.org/wiki/Succinct_data_structure

Specifically, you can modify Emils (first) solution to remove the pop count operation and replace it with a lookup table (for the details see the wiki article). By reducing the size of a block to (log n)/2 bits, the lookup table uses o(n) bits.