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

• @EmilJeřábek - I want the algorithm to use $O(n)$ bits (linear in the input size), not $O(n)$ memory words. Does it makes sense? – R B Feb 24 '16 at 14:37
• I see, thanks for clarification. Now, another question: what operations can you do in constant time on memory words? Here’s a candidate algorithm: split the array in $(\log n)$-size blocks, and for each block $b$, store the content of $b$ as one word, and the count of set bits before $b$ as another word. This makes $O(n)$ bits. Each query can be answered by examining four words, and it can be computed using $O(1)$ operations on these words such as shifts, subtraction, and (most importantly) population count. Does your model allow this? – Emil Jeřábek Feb 24 '16 at 15:05
• @EmilJeřábek - I had only arithmetic operations, indexing and bit lookups (i.e., looking a specific bit out of a word) in mind. Standard bit operations such as shifts can also be considered. I agree that if we could count the number of set bits in $O(1)$ then your algorithm indeed solves the problem. – R B Feb 24 '16 at 15:43
• The problem comes from an algorithm we are building for interval-sum queries over sliding windows. That is, we have a stream of integers, each in ${0,1,\ldots, R}$ and we wish to approximate the sum of a given interval. Our problem then reduces to exact interval count on a (much smaller) binary array (which also slides''). For a $n$-sized binary sliding window, we use $O(n)$ bits, add a bit in amortized constant time and perform queries in $O(\log n)$. I was wondering if constant time queries is feasible, even if the array is not updated. – R B Feb 24 '16 at 15:49
• @EmilJeřábek - thanks for your suggestion and analysis ! This can be an answer for the question, even though it doesn't fully answer our needs. The $O(n)$ bits space is a hard constraint for us, and we wish to show that no algorithm such algorithm can answer queries in constant time. – R B Feb 24 '16 at 15:52

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.

• (* facepalm *) Lookup table, obviously. Why didn't I think of that. – Emil Jeřábek Feb 24 '16 at 20:31
• In view of the OP's comment above, it's worth noting that the structure can be easily implemented as a sliding window so that moving the window by one bit (or even block) also takes constant time. – Emil Jeřábek Feb 24 '16 at 22:08
• @EmilJeřábek - translating your solution to the sliding window setting isn't straight forward. Instead of counting the number of set bits in the entire array-part that precedes the current block, we need to count the number of set bits within the sliding window that precedes this block, which doesn't seem doable in constant time. Am I missing anything? – R B Feb 25 '16 at 9:17
• No, you don't need to do that. Since you will ultimately subtract the count for $x$ from the count for $y$, it doesn't matter if all the stored counts are off by a fixed amount; in other words, the left edge of the sliding window can be assigned an arbitrary count. Thus, when moving the window, you only need to update the count for the block where the new element resides. From time to time, you need to reduce all the counts so that they do not occupy too much space, but this little work can be easily distributed so that it only takes O(1) time per any given query. – Emil Jeřábek Feb 25 '16 at 11:07
• Actually, the nuisance in the last sentence can be elegantly avoided altogether by computing all counts modulo a fixed number greater than $n$. – Emil Jeřábek Feb 25 '16 at 12:13

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

1. space $O(n\log^{(k)}n)$ and query time $O(1)$ for any constant $k$;

2. space $O(n)$ and query time $\tilde O(\log^*n)$.

The algorithms work as follows. There are parameters $k>0$ and $n=b_0>b_1>\dots>b_k>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<i<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$.

Turns out that not only that this is doable in $O(n)$ memory bits as proposed in Benjamin Sach's answer, this can actually be done in $n\cdot(1+o(1))$ bits.

The idea is to think of the $n$-bits input as the characteristic vector of a subset of $\{1,2,\ldots,n\}$ (i.e., the $i'th$ bit is set iff $i$ is in the set). Then, we can simply use a succinct dictionary to represent the set with the required number of bits.