Lazy data structure for two-pointers

Revision en4, by Svlad_Cjelli, 2024-09-12 21:11:49

I ran into a clever trick while reading the solutions here https://codeforces.me/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)$$$.
  • EDIT: we can decrement l too! Just compute $$$f(l-1, m)$$$ and push to the front of the list. This doesn't break the amortized performance because we never decrement $$$m$$$.

That's it!

Note that this requires we never increment $$$r$$$, so it doesn't fit every problem.

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Svlad_Cjelli 2024-09-12 21:11:49 225
en3 English Svlad_Cjelli 2024-09-12 20:15:05 0 Tiny change: 'l=m=r=0$ .Then:\n- to inc' -> 'l=m=r=0$ . Then:\n\n- to inc' (published)
en2 English Svlad_Cjelli 2024-09-12 20:13:31 3 Tiny change: 'l=m=r=0$ .Then:\n- to inc' -> 'l=m=r=0$ . Then:\n\n- to inc'
en1 English Svlad_Cjelli 2024-09-12 20:12:46 2124 Initial revision (saved to drafts)