# Maintaining the product of a queue of semigroup elements

I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time. The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication. Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$. I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?

• Just a comment, since this problem has already been solved. We can use a finger tree (a clear overkill) to solve this problem too. staff.city.ac.uk/~ross/papers/FingerTree.html Commented Nov 12, 2014 at 4:30

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )

About how to maintain on stacks:

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case.

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need.

When pop, simply delete $p_n$ and $s_n$.

When push, $p_{n+1}=p_n s_{n+1}$.

• Could you explain how it is easier with two stacks? Commented Aug 16, 2013 at 5:17
• That's so great! I was stuck thinking about complicated tree solutions, so reading this solution was a wonderful surprise. Commented Aug 16, 2013 at 6:47
• Thanks @GeoffreyIrving . I threw a gist up. Only gotcha I ran into was that you have to watch the order of multiplication when inserting to the outbox product stack. gist.github.com/chadbrewbaker/6253415 Commented Aug 16, 2013 at 20:52
• This seems to require $O(n)$ extra space to store the 'partial products' - is that a necessity of the algorithm or do you know if there are solutions using $O(1)$ additional space? Commented Aug 17, 2013 at 1:05
• @StevenStadnicki one can do it with $O(\sqrt{n})$ extra 'partial products' space. Basically only store the partial product from $x_1$ to $x_k$ where $k$ is a perfect square. (and apply some common amortization tricks) Commented Nov 13, 2014 at 2:13

I would memoize the partial products:

{.}{..}{....}{........}{....}{..}{.}

On the incoming end you combine them as they grow to a size equal to their left neighbor. On the outgoing end you spit them in half until you get one element. Amoritized work is log(n) per update to maintain the total product.

• If you go to a tree solution, there's no need for amortized complexity: worst case $O(\log n)$ is easy. Commented Aug 16, 2013 at 18:19
• When you memoize the products like this you take a O(n) hit on the update where the big chunk in the middle gets split apart. Commented Aug 16, 2013 at 20:06
• Yes, that is why I asked for amortized complexity. The $O(n)$ hit can be charged to insertions to restore $O(1)$ time. Commented Aug 16, 2013 at 20:36
• Oh, I see. Yes, your tree solution is only amortized $O(\log n)$ time, but it's easy to make it worst case $O(\log n)$. Give each entry a unique fixed index, make a complete binary tree over all indices, and store only the portion of the tree that overlaps with the current queue. When you want to compute the product, traverse the current portion of the tree, which will have $O(\log n)$ depth. The tree structure changes in at most $O(\log n)$ places for insertions and removals. Commented Aug 16, 2013 at 20:40