<p>I would memoize the partial products:</p>

<p>{.}{..}{....}{........}{....}{..}{.}</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-16T18:19:59.457Z
If you go to a tree solution, there's no need for amortized complexity: worst case $O(\log n)$ is easy.
Geoffrey Irving
CC BY-SA 3.0
2013-08-16T20:06:47.963Z
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.
Chad Brewbaker
CC BY-SA 3.0
2013-08-16T20:36:40.623Z
Yes, that is why I asked for amortized complexity.  The $O(n)$ hit can be charged to insertions to restore $O(1)$ time.
Geoffrey Irving
CC BY-SA 3.0
2013-08-16T20:40:51.123Z
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.
Geoffrey Irving
CC BY-SA 3.0
2013-08-16T15:47:16.113Z
2013-08-16T20:03:26.590Z
2013-08-16T20:03:26.590Z
Chad Brewbaker
<p>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. </p>

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

<hr>

<p>About how to maintain on stacks: </p>

<p>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. </p>

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

<p>When pop, simply delete $p_n$ and $s_n$. </p>

<p>When push, $p_{n+1}=p_n s_{n+1}$. </p>

CC BY-SA 3.0
2013-08-16T05:17:28.643Z
Could you explain *how* it is easier with two stacks?
Huck Bennett
CC BY-SA 3.0
2013-08-16T06:47:30.940Z
That's so great!  I was stuck thinking about complicated tree solutions, so reading this solution was a wonderful surprise.
Geoffrey Irving
CC BY-SA 3.0
2013-08-16T15:55:53.113Z
Need to see an example. I can see using a log number of stacks but not two.
Chad Brewbaker
CC BY-SA 3.0
2013-08-16T17:10:47.247Z
Chad: This question may help: http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks
Geoffrey Irving
CC BY-SA 3.0
2013-08-16T20:52:13.497Z
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. https://gist.github.com/chadbrewbaker/6253415
Chad Brewbaker
CC BY-SA 3.0
2013-08-17T01:05:07.520Z
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?
Steven Stadnicki
CC BY-SA 3.0
2013-09-01T20:21:02.623Z
@sevenkplus: Would you like me to use "sevenkplus" or a different name when acknowledging this answer in a paper?  Thanks!
Geoffrey Irving
CC BY-SA 3.0
2013-09-05T18:29:09.913Z
@GeoffreyIrving: "sevenkplus" is OK.
Yuzhou Gu
CC BY-SA 3.0
2014-11-13T02:13:32.913Z
@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)
Chao Xu
CC BY-SA 3.0
2014-11-19T20:29:19.240Z
@StevenStadnicki It's so hard to find a reference for this, took me a while to find the right keyword to search. It is impossible. [Space-time tradeoffs for linear recursion](http://link.springer.com/article/10.1007%2FBF01744566). However, you can get $O(n^\epsilon)$ extra space for $O(1/\epsilon)$ time.
Chao Xu
CC BY-SA 3.0
2013-08-16T04:25:38.933Z
2013-08-16T05:51:21.887Z
2013-08-16T05:51:21.887Z
Yuzhou Gu
<p>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</p>

<p>$$\prod Q = s_1 \cdots s_n.$$</p>

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

CC BY-SA 3.0
2014-11-12T04:30:31.103Z
Just a comment, since this problem has already been solved. We can use a finger tree (a clear overkill) to solve this problem too. http://staff.city.ac.uk/~ross/papers/FingerTree.html
Chao Xu
<online-algorithms><amortized-analysis>
Maintaining the product of a queue of semigroup elements
Geoffrey Irving
# Maintaining the product of a queue of semigroup elements

(Asked by: username_0 on 2013-08-16)

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?

**Tags:** online-algorithms, amortized-analysis
> **Comments:**
> **username_1**: Just a comment, since this problem has already been solved. We can use a finger tree (a clear overkill) to solve this problem too. http://staff.city.ac.uk/~ross/papers/FingerTree.html  

---

## 2 answers

### Answer by username_3 on 2013-08-16. Score: 7 | Accepted answer

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}$.

> **Comments:**
> **username_4**: Could you explain *how* it is easier with two stacks?  
> **username_0**: That's so great!  I was stuck thinking about complicated tree solutions, so reading this solution was a wonderful surprise.  
> **username_2**: Need to see an example. I can see using a log number of stacks but not two.  
> **username_0**: Chad: This question may help: http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks  
> **username_2**: 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. https://gist.github.com/chadbrewbaker/6253415  
> **username_5**: 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?  
> **username_0**: @sevenkplus: Would you like me to use "sevenkplus" or a different name when acknowledging this answer in a paper?  Thanks!  
> **username_3**: @GeoffreyIrving: "sevenkplus" is OK.  
> **username_1**: @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)  
> **username_1**: @StevenStadnicki It's so hard to find a reference for this, took me a while to find the right keyword to search. It is impossible. [Space-time tradeoffs for linear recursion](http://link.springer.com/article/10.1007%2FBF01744566). However, you can get $O(n^\epsilon)$ extra space for $O(1/\epsilon)$ time.  

---

### Answer by username_2 on 2013-08-16. Score: -1

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.

> **Comments:**
> **username_0**: If you go to a tree solution, there's no need for amortized complexity: worst case $O(\log n)$ is easy.  
> **username_2**: 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.  
> **username_0**: Yes, that is why I asked for amortized complexity.  The $O(n)$ hit can be charged to insertions to restore $O(1)$ time.  
> **username_0**: 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.  

---

