A Slight Generalization of Push-Free Segment Trees

Правка en1, от WLZ, 2024-01-30 11:48:35

Hi everyone!

I'd like to share a simple way to use the push-free segment tree in some cases where the updates aren't commutative (spoiler: they need to be invertible). The uses cases of this trick are rather limited, though.

The problem

We want to solve the following problem: Given an array $$$a_0, a_1, \dots, a_{N-1}$$$, whose elements satisfy certain properties (see here), answer $$$Q$$$ queries of the following types:

  • (Range queries): Given $$$0 \leq l < r \leq N$$$, find $$$a_l \cdot a_{l+1} \cdots a_{r-1}$$$ (endpoints are left inclusive and right exclusive).
  • (Range updates): Given $$$0 \leq l < r \leq N$$$ and a mapping $$$f$$$, update $$$a_i$$$ to $$$f(a_i)$$$ for all $$$i \in [l, r)$$$. $$$f$$$ has to satisfy the properties described here.

Push-free segment trees

Briefly, this is how the push-free segment tree works: We keep two arrays: $$$d$$$ (the nodes) and $$$lz$$$ (the lazy tags). Then the operations work as follows:

  • Updates: Find the nodes corresponding to the range $$$[l, r)$$$. Let these nodes be $$$v_1$$$, ..., $$$v_k$$$. For every node $$$v_i$$$, update $$$d_{v_i}$$$ to $$$f(d_{v_i})$$$, and set $$$lz_{v_i}$$$ to $$$f \circ lz_{v_i}$$$. Then, for every node $$$v$$$ that is the ancestor of some $$$v_i$$$, update it using its children (i.e. set $$$d_v = d_l \circ d_r$$$ where $$$l$$$ and $$$r$$$ are the children of $$$v$$$).
  • Queries: Let $$$v_1, \dots, v_k$$$ be the nodes corresponding to $$$[l, r)$$$. For every $$$v_i$$$, let $$$w_1, \dots, w_m$$$ be its ancestors from top to bottom ($$$w_m$$$ is the parent of $$$v_i$$$). Let $$$ans_i = (lz_{w_1} \circ \cdots \circ lz_{w_m})(d_{v_i})$$$. Then the answer is $$$ans_1 \cdot ans_2 \cdots ans_k$$$.

Due to the specific structure of the segment tree, the number of nodes considered in each query/update is small, which makes the operations efficient.

This is correct if we add the additonal assumption that lazy tags are commutative, i.e. $$$f(g(x)) = g(f(x))$$$ for all $$$f, g \in F$$$ and $$$x \in S$$$.

The algorithm

We drop the commutative assumption and add a new assumption: invertibility. This means that for all $$$f \in F$$$ there must be some $$$f^{-1} \in F$$$ such that $$$f(f^{-1}(x)) = f^{-1}(f(x))$$$ for all $$$x \in S$$$. Note that the inverse operation needs to be implemented explicitly.

The invertible case is just a simple modification of the above:

  • Updates: Find the $$$v_1, \dots, v_k$$$. Again, for each $$$v_i$$$, let $$$w_1, \dots, w_m$$$ be the ancestors. Let $$$g = lz_{w_1} \circ \cdots \circ lz_{w_k}$$$, and let $$$h = g^{-1} \circ f \circ g$$$ (this looks a lot like conjugation!). Then update $$$d_{v_i}$$$ to $$$h(d_{v_i})$$$ and $$$lz_{v_i}$$$ to $$$h \circ lz_{v_i}$$$.
  • Queries: Exactly the same as before!

Essentially, the $$$g^{-1} \circ f \circ g$$$ cancels the previous lazy tags, inserts $$$f$$$ before them and adds them back. I suggest trying some small examples yourself to see this in action.

A recursive implementation can be found here.

Example problems

Non-commutative invertible lazy tags aren't very common in competitive programming, but there are still a few examples out there.

I'm using the following interface to implement the operations in C++:

Code

This basically the same as the AtCoder Library interface, except that I let e and id be constants instead of functions and added the inv function.

Example 1

Library Checker — Range Affine Range Sum

Problem: Given an array $$$a_0$$$, $$$a_1$$$, ..., $$$a_{N-1}$$$. Answer $$$Q$$$ queries of the following types:

  • Given $$$0 \leq l < r \leq N$$$, find $$$a_l + a_{l+1} + \dots + a_{r-1}$$$ modulo $$$998244353$$$.
  • Given $$$0 \leq l < r \leq N$$$ and $$$b$$$, $$$c$$$ ($$$b \ne 0$$$), update $$$a_i$$$ to $$$b \cdot a_i + c$$$ for all $$$l \leq i < r$$$.

The inverse of $$$f(x) = bx + c$$$ is $$$f^{-1}(x) = \frac x b - \frac c b$$$. Note that the condition $$$b \ne 0$$$ is crucial for inverses to exist.

For an explanation on how to implement the operations, check out the the last section here.

Here is the C++ implementation:

Code

(I'm using the AtCoder modint implementation)

Example 2

Here's another example I came up with (no place to submit, unfortunately).

Problem: Let $$$k$$$ be a fixed integer. We have an array of $$$a$$$ of $$$N$$$ $$$k$$$-tuples. Answer $$$Q$$$ queries of the following types:

  • Given $$$0 \leq l < r \leq N$$$, find $$$a_l + a_{l+1} + \dots + a_{r-1}$$$. (Addition of tuples is done element-wise)
  • Given $$$0 \leq l < r \leq N$$$ and a permutation $$$\sigma$$$ of $$$k$$$ elements, update $$$a_i$$$ to $$$\sigma(a_i)$$$ for all $$$l \leq i < r$$$.

Note that permutation composition is generally not commutative, but a permutation always has an inverse.

Here are the operations in C++ (I set $$$k$$$ to $$$10$$$ for concreteness):

Code

Benchmarks

Here are some benchmarks against the iterative implementation by AtCoder and a recursive lazy segment tree implementation.

Library Checker — Range Affine Range Sum

Implementation AtCoder Recursive Push-free
Time 762 ms 839 ms 1127 ms
Unfortunately, the push-free segment tree is slower, mainly due to the requirement of modular inverses in the inv function.

As for the second example problem, I benchmarked it using some self-generated cases. I set $$$k = 10$$$. These were the results:

Implementation AtCoder Recursive Push-free
$$$N = Q = 2 \times 10^5$$$ (link) 568 ms 567 ms 412 ms
$$$N = Q = 2^{18}$$$ (link) 749 ms 758 ms 633 ms
$$$N = Q = 2^{19}$$$ (link) 1577 ms 1707 ms 1350 ms
In this case, the push-free segment tree turns out to be faster! So this algorithm is not completely useless after all.

You can see that I didn't do the benchmark very carefully, so there may be special cases where the push-free segment tree is much slower. If you know of any such cases, please let me know.

Thank you for reading! I will end this post with a few things that still need to be answered:

  • Extend this to 2 dimensions.
  • Implement this algorithm iteratively instead of recursively.
  • Are push-free segment trees possible when the updates aren't commutative or invertible?
Теги segment trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский WLZ 2024-01-30 11:48:35 8762 Initial revision (published)