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++:

struct S { ... }; // Segment tree element type
const S e = ...; // The identity element
S op(S a, S b) { ... } // Compute a · b

struct F { ... }; // Lazy mapping type
const F id = ...; // The identity mapping
S mapping(F f, S x) { ... } // Compute f(x)
F composition(F f, F g) { ... } // Compute f ∘ g
F inv(F f) { ... } // Compute f^(-1)

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:

using mint = atcoder::modint998244353;

struct S { mint a; int size; };
const S e = {0, 0};
S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }

struct F { mint a, b; };
S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }
F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }
F inv(F f) { mint a_inv = f.a.inv(); return {a_inv, -f.b * a_inv}; }

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

constexpr int K = 10;

using S = array<long long, K>;
S op(S a, const S &b) {
    for (int i = 0; i < K; i++) a[i] += b[i];
    return a;
}
constexpr S e = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

using F = array<int, K>;
S mapping(const F &f, const S &x) {
    S y;
    for (int i = 0; i < K; i++) y[f[i]] = x[i];
    return y;
}
F composition(const F &f, const F &g) {
    F h;
    for (int i = 0; i < K; i++) h[i] = f[g[i]];
    return h;
}
F inv(const F &f) {
    F g;
    for (int i = 0; i < K; i++) g[f[i]] = i;
    return g;
}
constexpr F id = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Benchmarks

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

Library Checker — Range Affine Range Sum

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

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?