3
$\begingroup$

Suppose I have a sequence of elements $a_1,\ldots,a_n$ in a group and I want to compute, for varying $1\leq i\leq j\leq n$, the product $b_{i,j}:=\Pi_{i\leq k\leq j}a_k$. Then I can do a precomputation of all $b_{1,j}$ and later determine each needed $b_{i,j}$ as $(b_{1,i-1})^{-1}b_{1,j}$.

The cost is $O(n)$ group operations and $O(n)$ additional time for the precomputation, and $O(1)$ operations and $O(1)$ additional time for each access. Clearly optimal. So far so good.

Now what if I don't have inverses (that is I have a monoid instead of a group)? The best I can come up with is a binary-tree like precomputed data structure. The cost of access would increase to $O(\log n)$. Can that be improved?

$\endgroup$
  • $\begingroup$ Interesting question! 1. Do you want a generic algorithm that works for any monoid (using only the monoid operations, but without knowing anything about the structure of the monoid)? Or do you have a particular monoid you are interested in? In the latter case it might be possible to do better than a generic algorithm. 2. There are probably uninteresting algorithms that spend a lot more during the precomputation in exchange for speeding up the access time a bit. I'm guessing those aren't of much interest to you, but do tell us if you are interested in those directions. $\endgroup$ – D.W. Dec 8 '17 at 2:57
  • $\begingroup$ The question is mostly from curiosity, so in principle I am interested in improvements along all kinds of directions. Originally, it came from matrix multiplication. $\endgroup$ – kne Dec 8 '17 at 19:15
2
$\begingroup$

As you say, with $O(n)$ precomputation you can arrange that each access takes $O(\log n)$ time. You build a binary tree over the elements, and annotate each internal node with the product of the leaves under it. This takes $O(n)$ precomputation and $O(n)$ storage.

If you are willing to do more precomputation, you can reduce the access time. In particular, with $O(n \log n)$ precomputation and $O(n \log n)$ storage, you can arrange that each access runs in $O(1)$ time. The idea is outlined below.


Notationally, we will let $b_{i,j}$ denote the product $a_i a_{i+1} \cdots a_j$, as you define in your question.

First, precompute the products $b_{i,n/2-1}$ for $i=1,2,\dots,n/2-1$ and the products $b_{n/2,j}$ for $j=n/2,\dots,n-1,n$. This can be done with a $O(n)$ precomputation. This will let you compute any product $b_{i,j}$ in $O(1)$ time if we have $i < n/2 \le n/2$, i.e., if the range $[i,j]$ spans the midpoint.

We still need a way to handle ranges that don't span the midpoint. We'll handle that recursively. Basically, take the sequence $a_1,\dots,a_{n/2-1}$ and recursively build a data structure for it (e.g., find its midpoint $a_{n/4}$, etc.). Also, recursively build a data structure for $a_{n/2},\dots,a_n$. This will let us compute all products $b_{i,j}$ where $j<n/2$ or $i\ge n/2$, i.e., where the range $[i,j]$ doesn't span the midpoint. This covers all the cases.

How much time does the precomputation take? If $T(n)$ denotes the time for the entire precomputation, it satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n),$$

which solves to $T(n) = O(n \log n)$. Similarly, we can see that the amount of storage needed is also $O(n \log n)$. Finally, this data structure will let you compute any product $b_{i,j}$ in $O(1)$ time.

(I'll let you figure out how to compute $b_{i,j}$ from this data structure in $O(1)$ time. It can be done with some clever bit-shifting tricks. It may help to think about the data structure in terms of the big-endian binary representation of the indices. For each index $i$, we compute $b_{i,i'}$ where $i,i'$ share a common prefix and then $i'$ is all ones after the common prefix; and we compute $b_{j',j}$ where $j',j$ share a common prefix and then $j'$ is all zeros after the common prefix. Given $i,j$, we can find the longest common prefix of $i,j$, then express as the product $b_{i,j} = b_{i,i'} b_{j',j}$, look up the values of $b_{i,i'}$ and $b_{j',j}$, and compute the product. All of these can be done in $O(1)$ time by placing the precomputed values in an array in the correct order.)

$\endgroup$
  • $\begingroup$ Thank you for your answer. I must admit, though, that I do not see how to achieve the lookup in $O(1)$. As far as I can tell I would have to compute $\lfloor\log_2(i\oplus j)\rfloor$, where $\oplus$ is XOR. But for the logarithm (number of significant digits) I need time $O(\log\log n)$. It would still be an improvement, of course. $\endgroup$ – kne Dec 11 '17 at 17:24
  • $\begingroup$ @kne, I think when I wrote this answer I was thinking we can take advantage of bit-twiddling tricks like x & (x-1) but I don't have time right now to reconstruct what I was thinking to check whether that's right or not. It's possible I might have been confused. Some architectures have en.wikipedia.org/wiki/Find_first_set which makes this easy. $\endgroup$ – D.W. Dec 11 '17 at 18:44
  • $\begingroup$ Ah, OK, I was not aware of any RAM model that has (an operation equivalent to) $\lfloor\log_2\rfloor$. $\endgroup$ – kne Dec 11 '17 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.