# Precomputation for partial products in monoids

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?

• 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. – D.W. Dec 8 '17 at 2:57
• 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. – kne Dec 8 '17 at 19:15

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

• 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. – kne Dec 11 '17 at 17:24
• @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. – D.W. Dec 11 '17 at 18:44
• Ah, OK, I was not aware of any RAM model that has (an operation equivalent to) $\lfloor\log_2\rfloor$. – kne Dec 11 '17 at 21:35