I ran into a clever trick while reading the solutions here https://mirror.codeforces.com/blog/entry/133382 (look at problem 2006C, "Implementation — Two Pointers")

The problem is: let's say there's an array $$$a$$$ and an associative operation $$${*}$$$ and we are interested in computing $$${f(l, r) := a_l * a_{l+1} * \ldots * a_r}$$$ , where we want to be able to increment $$$l$$$ or $$$r$$$ and easily recompute $$$f$$$. If we can do that, then we can solve all kinds of two-pointer-style problems.

If $$$f$$$ is invertible, e.g. addition, we can easily do this by just keeping track of a single aggregated value. But what if $$$f$$$ is something like $$$\gcd$$$? In this case, this simple solution won't work. But there is a trick.

With the simple solution, the hard part is incrementing $$$l$$$ because if we only keep the aggregated value for $$$f(l, r)$$$, we can't recover the value for $$$f(l+1, r)$$$. To do that we would ideally need to keep a list of values $$$f(l, r), f(l+1, r), \ldots, f(r,r)$$$ and then incrementing $$$l$$$ would just involve popping the front of the list. But then, incrementing $$$r$$$ is hard because we'd need to recompute the whole list.

To combine these two approaches, we keep $$$f(l, m), f(l+1, m), \ldots, f(m, m)$$$ for some intermediate $$$m$$$, and also $$$f(m+1, r)$$$. In the beginning, $$$l=m=r=0$$$ . Then:

• to increment $$$r$$$ we simply recompute the tail value by taking $$$f(m+1, r+1)=f(m+1, r) * a_{r+1}$$$
• to increment $$$l$$$:
  • if $$$l < m$$$ we pop the list.
  • otherwise, $$$l = m$$$. We set $$$m := r$$$, and recompute the whole list from $$$l$$$ to $$$r$$$. This may seem slow but the subarrays recomputed in this manner don't overlap and therefore this has amortized constant cost.
• to query $$$f(l, r)$$$ we simply compute $$$f(l, m) * f(m+1, r)$$$.

That's it!

Note that this requires we only increment the bounds, which is useful only for some problems.

Does this trick have a name? Is it "lore"? I haven't seen it before. But it's been a while since I've done a contest (hard to find time these days...) so maybe it's already well known. For those who haven't seen it, hopefully you find it interesting!