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++:
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:
(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):
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 |
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 |
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?