Persistent segment tree with lazy propagation (tools/persistent_lazy_segtree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-21 00:01:45+09:00
• Include: #include "tools/persistent_lazy_segtree.hpp"

It is the data structure for the pair of a monoid $(S, \cdot: S \times S \to S, e \in S)$ and a set $F$ of $S \to S$ mappings that satisfies the following properties.

• $F$ contains the identity map $\mathrm{id}$, where the identity map is the map that satisfies $\mathrm{id}(x) = x$ for all $x \in S$.
• $F$ is closed under composition, i.e., $f \circ g \in F$ holds for all $f, g \in F$.
• $f(x \cdot y) = f(x) \cdot f(y)$ holds for all $f \in F$ and $x, y \in S$.

Given an array $S$ of length $N$, it processes the following queries in $O(\log N)$ time.

• Acting the map $f\in F$ (cf. $x = f(x)$) on all the elements of an interval
• Calculating the product of the elements of an interval

For simplicity, in this document, we assume that the oracles op, e, mapping, composition, and id work in constant time. If these oracles work in $O(T)$ time, each time complexity appear in this document is multipled by $O(T)$.

License

• CC0

Author

• anqooqie

Constructor of buffer

persistent_lazy_segtree<SM, FM, mapping>::buffer buffer();

It creates an empty buffer for tools::persistent_lazy_segtree<SM, FM, mapping>. It defines $S$ by typename SM::T, $\mathrm{op}$ by S SM::op(S x, S y), $\mathrm{e}$ by S SM::e(), $F$ by typename FM::T, $\mathrm{composition}$ by F FM::op(F f, F g), $\mathrm{id}$ by F FM::e() and $\mathrm{mapping}$ by S mapping(F f, S x).

Constraints

• None

Time Complexity

• $O(1)$

Constructor

(1) persistent_lazy_segtree<SM, FM, mapping> a(persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, long long l_star, long long r_star);
(2) persistent_lazy_segtree<SM, FM, mapping> a(persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, long long l_star, long long r_star, S x);
(3) persistent_lazy_segtree<SM, FM, mapping> a(persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, std::ranges::range v);

• (1)
  • It creates an array $(a_{l^\ast}, a_{l^\ast + 1}, \ldots, a_{r^\ast - 1})$. All the elements are initialized to e().
• (2)
  • It creates an array $(a_{l^\ast}, a_{l^\ast + 1}, \ldots, a_{r^\ast - 1})$. All the elements are initialized to x.
• (3)
  • It creates an array $(a_0, a_1, \ldots, a_{|v| - 1})$, initialized to v.

The data will be stored on buffer.

Constraints

• $\forall x \in S. \forall y \in S. \forall z \in S. \mathrm{op}(\mathrm{op}(x, y), z) = \mathrm{op}(x, \mathrm{op}(y, z))$
• $\forall x \in S. \mathrm{op}(\mathrm{e}(), x) = \mathrm{op}(x, \mathrm{e}()) = x$
• $\forall f \in F. \forall g \in F. \forall h \in F. \mathrm{composition}(\mathrm{composition}(f, g), h) = \mathrm{composition}(f, \mathrm{composition}(g, h))$
• $\forall f \in F. \mathrm{composition}(\mathrm{id}(), f) = \mathrm{composition}(f, \mathrm{id}()) = f$
• $\forall f \in F. \forall x \in S. \forall y \in S. \mathrm{mapping}(f, \mathrm{op}(x, y)) = \mathrm{op}(f(x), f(y))$
• buffer has not been used so far.
• $-4 \times 10^{18} \leq l^\ast \leq r^\ast \leq 4 \times 10^{18}$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

lower_bound

long long a.lower_bound();

It returns $l^\ast$.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$

upper_bound

long long a.upper_bound();

It returns $r^\ast$.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$

set

persistent_lazy_segtree<SM, FM, mapping> a.set(long long p, S x);

It creates $b$, a copy of $a$, assigns $x$ to $b_p$ and returns $b$.

Constraints

• buffer is in its lifetime.
• $l^\ast \leq p < r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

get

S a.get(long long p);

It returns $a_p$.

Constraints

• buffer is in its lifetime.
• $l^\ast \leq p < r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

prod

S a.prod(long long l, long long r);

It returns $\mathrm{op}(a_l, \ldots, a_{r - 1})$, assuming the properties of the monoid. It returns $\mathrm{e}()$ if $l = r$.

Constraints

• buffer is in its lifetime.
• $l^\ast \leq l \leq r \leq r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

all_prod

S a.all_prod();

It returns $\mathrm{op}(a_{l^\ast}, \ldots, a_{r^\ast - 1})$, assuming the properties of the monoid. It returns $\mathrm{e}()$ if $l^\ast = r^\ast$.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$

apply

(1) persistent_lazy_segtree<SM, FM, mapping> a.apply(long long p, F f);
(2) persistent_lazy_segtree<SM, FM, mapping> a.apply(long long l, long long r, F f);

• (1)
  • It creates $b$, a copy of $a$, assigns $\mathrm{mapping}(f, b_p)$ to $b_p$ and returns $b$.
• (2)
  • It creates $b$, a copy of $a$, assigns $\mathrm{mapping}(f, b_i)$ to $b_i$ for all $i$ such that $l \leq i < r$ and returns $b$.

Constraints

• buffer is in its lifetime.
• (1)
  • $l^\ast \leq p < r^\ast$
• (2)
  • $l^\ast \leq l \leq r \leq r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

rollback

persistent_lazy_segtree<SM, FM, mapping> a.rollback(persistent_lazy_segtree<SM, FM, mapping> s, long long l, long long r);

It creates $b$, a copy of $a$, assigns $\mathrm{mapping}(f, s_i)$ to $b_i$ for all $i$ such that $l \leq i < r$ and returns $b$.

Constraints

• buffer is in its lifetime.
• a and s shares the same buffer.
• $l^\ast \leq l \leq r \leq r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

max_right

long long a.max_right<G>(long long l, G g)

It returns an index $r$ that satisfies both of the followings.

• $r = l$ or $g(\mathrm{op}(a_l, a_{l + 1}, \ldots, a_{r - 1})) = \top$
• $r = r^\ast$ or $g(\mathrm{op}(a_l, a_{l + 1}, \ldots, a_r)) = \bot$

If $g$ is monotone, this is the maximum $r$ that satisfies $g(\mathrm{op}(a_l, a_{l + 1}, \ldots, a_{r - 1})) = \top$.

Constraints

• buffer is in its lifetime.
• The function object that takes S as the argument and returns bool should be defined.
• if g is called with the same argument, it returns the same value, i.e., g has no side effect.
• $g(\mathrm{e}()) = \top$
• $l^\ast \leq l \leq r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

min_left

long long a.min_left<G>(long long r, G g)

It returns an index $l$ that satisfies both of the followings.

• $l = r$ or $g(\mathrm{op}(a_l, a_{l + 1}, \ldots, a_{r - 1})) = \top$
• $l = l^\ast$ or $g(\mathrm{op}(a_{l - 1}, a_{l + 1}, \ldots, a_{r - 1})) = \bot$

If $g$ is monotone, this is the minimum $l$ that satisfies $g(\mathrm{op}(a_l, a_{l + 1}, \ldots, a_{r - 1})) = \top$.

Constraints

• buffer is in its lifetime.
• The function object that takes S as the argument and returns bool should be defined.
• if g is called with the same argument, it returns the same value, i.e., g has no side effect.
• $g(\mathrm{e}()) = \top$
• $l^\ast \leq r \leq r^\ast$

Time Complexity

• $O(\log (r^\ast - l^\ast))$

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• Fixed point combinator (tools/fix.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)

Verified with

• tests/persistent_lazy_segtree/binary_search.test.cpp
• tests/persistent_lazy_segtree/prod_apply_and_rollback.test.cpp

Code

#ifndef TOOLS_PERSISTENT_LAZY_SEGTREE_HPP
#define TOOLS_PERSISTENT_LAZY_SEGTREE_HPP

#include <algorithm>
#include <array>
#include <cassert>
#include <functional>
#include <numeric>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#include "tools/ceil_log2.hpp"
#include "tools/fix.hpp"

namespace tools {
  template <typename SM, typename FM, auto mapping>
  class persistent_lazy_segtree {
    using S = typename SM::T;
    using F = typename FM::T;
    static_assert(
      ::std::is_convertible_v<decltype(mapping), ::std::function<S(F, S)>>,
      "mapping must work as S(F, S)");

    struct node {
      S data;
      F lazy;
      ::std::array<int, 2> children;
    };

  public:
    class buffer {
      ::std::vector<::tools::persistent_lazy_segtree<SM, FM, mapping>::node> m_nodes;
      long long m_offset;
      long long m_size;
      int m_height;

    public:
      friend ::tools::persistent_lazy_segtree<SM, FM, mapping>;
    };

  private:
    ::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer *m_buffer;
    int m_root;

    long long capacity() const {
      return 1LL << this->m_buffer->m_height;
    }

  public:
    persistent_lazy_segtree() = default;
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, const long long l_star, const long long r_star) :
      persistent_lazy_segtree(buffer, l_star, r_star, SM::e()) {
    }
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, const long long l_star, const long long r_star, const S& x) : m_buffer(&buffer) {
      assert(buffer.m_nodes.empty());
      assert(l_star <= r_star);
      buffer.m_offset = l_star;
      buffer.m_size = r_star - l_star;
      buffer.m_height = ::tools::ceil_log2(::std::max(1LL, r_star - l_star));
      buffer.m_nodes.push_back({x, FM::e(), {-1, -1}});
      for (int k = 1; k <= buffer.m_height; ++k) {
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes.back().data, buffer.m_nodes.back().data), FM::e(), {k - 1, k - 1}});
      }
      this->m_root = buffer.m_height;
    }
    template <::std::ranges::range R>
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, R&& v) : m_buffer(&buffer) {
      assert(buffer.m_nodes.empty());
      for (auto&& x : v) {
        buffer.m_nodes.push_back({x, FM::e(), {-1, -1}});
      }
      buffer.m_offset = 0;
      buffer.m_size = buffer.m_nodes.size();
      buffer.m_height = ::tools::ceil_log2(::std::max(1LL, buffer.m_size));
      buffer.m_nodes.push_back({SM::e(), FM::e(), {-1, -1}});
      for (int h = 1; h <= buffer.m_height; ++h) {
        buffer.m_nodes.push_back({SM::e(), FM::e(), {static_cast<int>(buffer.m_nodes.size()) - 1, static_cast<int>(buffer.m_nodes.size()) - 1}});
      }
      this->m_root = ::tools::fix([&](auto&& dfs, const int h, const long long kl, const long long kr) -> int {
        assert(kl < kr);
        if (buffer.m_size <= kl) return buffer.m_size + h;
        if (h == 0) return kl;
        const auto km = ::std::midpoint(kl, kr);
        const auto left_child = dfs(h - 1, kl, km);
        const auto right_child = dfs(h - 1, km, kr);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(buffer.m_height, 0, this->capacity());
    }

    long long lower_bound() const {
      return this->m_buffer->m_offset;
    }
    long long upper_bound() const {
      return this->m_buffer->m_offset + this->m_buffer->m_size;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> set(long long p, const S& x) const {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      auto& buffer = *this->m_buffer;
      p -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> int {
        assert(kl < kr);
        if (p <= kl && kr <= p + 1) {
          buffer.m_nodes.push_back({x, FM::e(), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= p || p + 1 <= kl) {
          if (lz == FM::e()) return k;
          buffer.m_nodes.push_back({mapping(lz, buffer.m_nodes[k].data), FM::op(lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        const auto left_child = dfs(buffer.m_nodes[k].children[0], kl, km, next_lz);
        const auto right_child = dfs(buffer.m_nodes[k].children[1], km, kr, next_lz);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, 0, res.capacity(), FM::e());
      return res;
    }
    S get(const long long p) const {
      return this->prod(p, p + 1);
    }
    S prod(long long l, long long r) const {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return SM::e();
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      return ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return mapping(lz, buffer.m_nodes[k].data);
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(buffer.m_nodes[k].children[0], kl, km, next_lz));
        if (km < r) res = SM::op(res, dfs(buffer.m_nodes[k].children[1], km, kr, next_lz));
        return res;
      })(this->m_root, 0, this->capacity(), FM::e());
    }
    S all_prod() const {
      return this->m_buffer->m_nodes[this->m_root].data;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> apply(const long long p, const F& f) const {
      return this->apply(p, p + 1, f);
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> apply(long long l, long long r, const F& f) const {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return *this;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> int {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          const F modified_lz = FM::op(f, lz);
          buffer.m_nodes.push_back({mapping(modified_lz, buffer.m_nodes[k].data), FM::op(modified_lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= l || r <= kl) {
          if (lz == FM::e()) return k;
          buffer.m_nodes.push_back({mapping(lz, buffer.m_nodes[k].data), FM::op(lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        const auto left_child = dfs(buffer.m_nodes[k].children[0], kl, km, next_lz);
        const auto right_child = dfs(buffer.m_nodes[k].children[1], km, kr, next_lz);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, 0, res.capacity(), FM::e());
      return res;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> rollback(const ::tools::persistent_lazy_segtree<SM, FM, mapping>& s, long long l, long long r) const {
      assert(this->m_buffer == s.m_buffer);
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return *this;
      if (l == this->lower_bound() && r == this->upper_bound()) return s;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k1, const int k2, const long long kl, const long long kr, const F& lz1, const F& lz2) -> int {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          if (lz2 == FM::e()) return k2;
          buffer.m_nodes.push_back({mapping(lz2, buffer.m_nodes[k2].data), FM::op(lz2, buffer.m_nodes[k2].lazy), buffer.m_nodes[k2].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= l || r <= kl) {
          if (lz1 == FM::e()) return k1;
          buffer.m_nodes.push_back({mapping(lz1, buffer.m_nodes[k1].data), FM::op(lz1, buffer.m_nodes[k1].lazy), buffer.m_nodes[k1].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz1 = FM::op(lz1, buffer.m_nodes[k1].lazy);
        const F next_lz2 = FM::op(lz2, buffer.m_nodes[k2].lazy);
        const auto left_child = dfs(buffer.m_nodes[k1].children[0], buffer.m_nodes[k2].children[0], kl, km, next_lz1, next_lz2);
        const auto right_child = dfs(buffer.m_nodes[k1].children[1], buffer.m_nodes[k2].children[1], km, kr, next_lz1, next_lz2);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, s.m_root, 0, res.capacity(), FM::e(), FM::e());
      return res;
    }
    template <typename G>
    long long max_right(long long l, const G& g) const {
      assert(this->lower_bound() <= l && l <= this->upper_bound());
      assert(g(SM::e()));
      if (l == this->upper_bound()) return l;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;

      return buffer.m_offset + ::std::min(::tools::fix([&](auto&& dfs, const S& c, const int k, const long long kl, const long long kr, const F& lz) -> ::std::pair<S, long long> {
        assert(kl < kr);
        if (kl < l) {
          assert(kl < l && l < kr);
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          if (l < km) {
            const auto [hc, hr] = dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
            assert(l <= hr && hr <= km);
            if (hr < km) return {hc, hr};
            return dfs(hc, buffer.m_nodes[k].children[1], km, kr, next_lz);
          } else {
            return dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
          }
        } else {
          if (const auto wc = SM::op(c, mapping(lz, buffer.m_nodes[k].data)); g(wc)) return {wc, kr};
          if (kr - kl == 1) return {c, kl};
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          const auto [hc, hr] = dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
          assert(l <= hr && hr <= km);
          if (hr < km) return {hc, hr};
          return dfs(hc, buffer.m_nodes[k].children[1], km, kr, next_lz);
        }
      })(SM::e(), this->m_root, 0, this->capacity(), FM::e()).second, buffer.m_size);
    }
    template <typename G>
    long long min_left(long long r, const G& g) const {
      assert(this->lower_bound() <= r && r <= this->upper_bound());
      assert(g(SM::e()));
      if (r == this->lower_bound()) return r;
      auto& buffer = *this->m_buffer;
      r -= buffer.m_offset;

      return buffer.m_offset + ::tools::fix([&](auto&& dfs, const S& c, const int k, const long long kl, const long long kr, const F& lz) -> ::std::pair<S, long long> {
        assert(kl < kr);
        if (r < kr) {
          assert(kl < r && r < kr);
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          if (km < r) {
            const auto [hc, hl] = dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
            assert(km <= hl && hl <= r);
            if (km < hl) return {hc, hl};
            return dfs(hc, buffer.m_nodes[k].children[0], kl, km, next_lz);
          } else {
            return dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
          }
        } else {
          if (const auto wc = SM::op(mapping(lz, buffer.m_nodes[k].data), c); g(wc)) return {wc, kl};
          if (kr - kl == 1) return {c, kr};
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          const auto [hc, hl] = dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
          assert(km <= hl && hl <= r);
          if (km < hl) return {hc, hl};
          return dfs(hc, buffer.m_nodes[k].children[0], kl, km, next_lz);
        }
      })(SM::e(), this->m_root, 0, this->capacity(), FM::e()).second;
    }
  };
}

#endif

#line 1 "tools/persistent_lazy_segtree.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <functional>
#include <numeric>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#line 1 "tools/ceil_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/fix.hpp"



#line 6 "tools/fix.hpp"

namespace tools {
  template <typename F>
  struct fix : F {
    template <typename G>
    fix(G&& g) : F({::std::forward<G>(g)}) {
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
      return F::operator()(*this, ::std::forward<Args>(args)...);
    }
  };

  template <typename F>
  fix(F&&) -> fix<::std::decay_t<F>>;
}


#line 15 "tools/persistent_lazy_segtree.hpp"

namespace tools {
  template <typename SM, typename FM, auto mapping>
  class persistent_lazy_segtree {
    using S = typename SM::T;
    using F = typename FM::T;
    static_assert(
      ::std::is_convertible_v<decltype(mapping), ::std::function<S(F, S)>>,
      "mapping must work as S(F, S)");

    struct node {
      S data;
      F lazy;
      ::std::array<int, 2> children;
    };

  public:
    class buffer {
      ::std::vector<::tools::persistent_lazy_segtree<SM, FM, mapping>::node> m_nodes;
      long long m_offset;
      long long m_size;
      int m_height;

    public:
      friend ::tools::persistent_lazy_segtree<SM, FM, mapping>;
    };

  private:
    ::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer *m_buffer;
    int m_root;

    long long capacity() const {
      return 1LL << this->m_buffer->m_height;
    }

  public:
    persistent_lazy_segtree() = default;
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, const long long l_star, const long long r_star) :
      persistent_lazy_segtree(buffer, l_star, r_star, SM::e()) {
    }
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, const long long l_star, const long long r_star, const S& x) : m_buffer(&buffer) {
      assert(buffer.m_nodes.empty());
      assert(l_star <= r_star);
      buffer.m_offset = l_star;
      buffer.m_size = r_star - l_star;
      buffer.m_height = ::tools::ceil_log2(::std::max(1LL, r_star - l_star));
      buffer.m_nodes.push_back({x, FM::e(), {-1, -1}});
      for (int k = 1; k <= buffer.m_height; ++k) {
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes.back().data, buffer.m_nodes.back().data), FM::e(), {k - 1, k - 1}});
      }
      this->m_root = buffer.m_height;
    }
    template <::std::ranges::range R>
    persistent_lazy_segtree(::tools::persistent_lazy_segtree<SM, FM, mapping>::buffer& buffer, R&& v) : m_buffer(&buffer) {
      assert(buffer.m_nodes.empty());
      for (auto&& x : v) {
        buffer.m_nodes.push_back({x, FM::e(), {-1, -1}});
      }
      buffer.m_offset = 0;
      buffer.m_size = buffer.m_nodes.size();
      buffer.m_height = ::tools::ceil_log2(::std::max(1LL, buffer.m_size));
      buffer.m_nodes.push_back({SM::e(), FM::e(), {-1, -1}});
      for (int h = 1; h <= buffer.m_height; ++h) {
        buffer.m_nodes.push_back({SM::e(), FM::e(), {static_cast<int>(buffer.m_nodes.size()) - 1, static_cast<int>(buffer.m_nodes.size()) - 1}});
      }
      this->m_root = ::tools::fix([&](auto&& dfs, const int h, const long long kl, const long long kr) -> int {
        assert(kl < kr);
        if (buffer.m_size <= kl) return buffer.m_size + h;
        if (h == 0) return kl;
        const auto km = ::std::midpoint(kl, kr);
        const auto left_child = dfs(h - 1, kl, km);
        const auto right_child = dfs(h - 1, km, kr);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(buffer.m_height, 0, this->capacity());
    }

    long long lower_bound() const {
      return this->m_buffer->m_offset;
    }
    long long upper_bound() const {
      return this->m_buffer->m_offset + this->m_buffer->m_size;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> set(long long p, const S& x) const {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      auto& buffer = *this->m_buffer;
      p -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> int {
        assert(kl < kr);
        if (p <= kl && kr <= p + 1) {
          buffer.m_nodes.push_back({x, FM::e(), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= p || p + 1 <= kl) {
          if (lz == FM::e()) return k;
          buffer.m_nodes.push_back({mapping(lz, buffer.m_nodes[k].data), FM::op(lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        const auto left_child = dfs(buffer.m_nodes[k].children[0], kl, km, next_lz);
        const auto right_child = dfs(buffer.m_nodes[k].children[1], km, kr, next_lz);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, 0, res.capacity(), FM::e());
      return res;
    }
    S get(const long long p) const {
      return this->prod(p, p + 1);
    }
    S prod(long long l, long long r) const {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return SM::e();
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      return ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return mapping(lz, buffer.m_nodes[k].data);
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(buffer.m_nodes[k].children[0], kl, km, next_lz));
        if (km < r) res = SM::op(res, dfs(buffer.m_nodes[k].children[1], km, kr, next_lz));
        return res;
      })(this->m_root, 0, this->capacity(), FM::e());
    }
    S all_prod() const {
      return this->m_buffer->m_nodes[this->m_root].data;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> apply(const long long p, const F& f) const {
      return this->apply(p, p + 1, f);
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> apply(long long l, long long r, const F& f) const {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return *this;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr, const F& lz) -> int {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          const F modified_lz = FM::op(f, lz);
          buffer.m_nodes.push_back({mapping(modified_lz, buffer.m_nodes[k].data), FM::op(modified_lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= l || r <= kl) {
          if (lz == FM::e()) return k;
          buffer.m_nodes.push_back({mapping(lz, buffer.m_nodes[k].data), FM::op(lz, buffer.m_nodes[k].lazy), buffer.m_nodes[k].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
        const auto left_child = dfs(buffer.m_nodes[k].children[0], kl, km, next_lz);
        const auto right_child = dfs(buffer.m_nodes[k].children[1], km, kr, next_lz);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, 0, res.capacity(), FM::e());
      return res;
    }
    ::tools::persistent_lazy_segtree<SM, FM, mapping> rollback(const ::tools::persistent_lazy_segtree<SM, FM, mapping>& s, long long l, long long r) const {
      assert(this->m_buffer == s.m_buffer);
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return *this;
      if (l == this->lower_bound() && r == this->upper_bound()) return s;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;
      r -= buffer.m_offset;

      auto res = *this;
      res.m_root = ::tools::fix([&](auto&& dfs, const int k1, const int k2, const long long kl, const long long kr, const F& lz1, const F& lz2) -> int {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          if (lz2 == FM::e()) return k2;
          buffer.m_nodes.push_back({mapping(lz2, buffer.m_nodes[k2].data), FM::op(lz2, buffer.m_nodes[k2].lazy), buffer.m_nodes[k2].children});
          return buffer.m_nodes.size() - 1;
        }
        if (kr <= l || r <= kl) {
          if (lz1 == FM::e()) return k1;
          buffer.m_nodes.push_back({mapping(lz1, buffer.m_nodes[k1].data), FM::op(lz1, buffer.m_nodes[k1].lazy), buffer.m_nodes[k1].children});
          return buffer.m_nodes.size() - 1;
        }
        const auto km = ::std::midpoint(kl, kr);
        const F next_lz1 = FM::op(lz1, buffer.m_nodes[k1].lazy);
        const F next_lz2 = FM::op(lz2, buffer.m_nodes[k2].lazy);
        const auto left_child = dfs(buffer.m_nodes[k1].children[0], buffer.m_nodes[k2].children[0], kl, km, next_lz1, next_lz2);
        const auto right_child = dfs(buffer.m_nodes[k1].children[1], buffer.m_nodes[k2].children[1], km, kr, next_lz1, next_lz2);
        buffer.m_nodes.push_back({SM::op(buffer.m_nodes[left_child].data, buffer.m_nodes[right_child].data), FM::e(), {left_child, right_child}});
        return buffer.m_nodes.size() - 1;
      })(res.m_root, s.m_root, 0, res.capacity(), FM::e(), FM::e());
      return res;
    }
    template <typename G>
    long long max_right(long long l, const G& g) const {
      assert(this->lower_bound() <= l && l <= this->upper_bound());
      assert(g(SM::e()));
      if (l == this->upper_bound()) return l;
      auto& buffer = *this->m_buffer;
      l -= buffer.m_offset;

      return buffer.m_offset + ::std::min(::tools::fix([&](auto&& dfs, const S& c, const int k, const long long kl, const long long kr, const F& lz) -> ::std::pair<S, long long> {
        assert(kl < kr);
        if (kl < l) {
          assert(kl < l && l < kr);
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          if (l < km) {
            const auto [hc, hr] = dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
            assert(l <= hr && hr <= km);
            if (hr < km) return {hc, hr};
            return dfs(hc, buffer.m_nodes[k].children[1], km, kr, next_lz);
          } else {
            return dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
          }
        } else {
          if (const auto wc = SM::op(c, mapping(lz, buffer.m_nodes[k].data)); g(wc)) return {wc, kr};
          if (kr - kl == 1) return {c, kl};
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          const auto [hc, hr] = dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
          assert(l <= hr && hr <= km);
          if (hr < km) return {hc, hr};
          return dfs(hc, buffer.m_nodes[k].children[1], km, kr, next_lz);
        }
      })(SM::e(), this->m_root, 0, this->capacity(), FM::e()).second, buffer.m_size);
    }
    template <typename G>
    long long min_left(long long r, const G& g) const {
      assert(this->lower_bound() <= r && r <= this->upper_bound());
      assert(g(SM::e()));
      if (r == this->lower_bound()) return r;
      auto& buffer = *this->m_buffer;
      r -= buffer.m_offset;

      return buffer.m_offset + ::tools::fix([&](auto&& dfs, const S& c, const int k, const long long kl, const long long kr, const F& lz) -> ::std::pair<S, long long> {
        assert(kl < kr);
        if (r < kr) {
          assert(kl < r && r < kr);
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          if (km < r) {
            const auto [hc, hl] = dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
            assert(km <= hl && hl <= r);
            if (km < hl) return {hc, hl};
            return dfs(hc, buffer.m_nodes[k].children[0], kl, km, next_lz);
          } else {
            return dfs(c, buffer.m_nodes[k].children[0], kl, km, next_lz);
          }
        } else {
          if (const auto wc = SM::op(mapping(lz, buffer.m_nodes[k].data), c); g(wc)) return {wc, kl};
          if (kr - kl == 1) return {c, kr};
          const auto km = ::std::midpoint(kl, kr);
          const F next_lz = FM::op(lz, buffer.m_nodes[k].lazy);
          const auto [hc, hl] = dfs(c, buffer.m_nodes[k].children[1], km, kr, next_lz);
          assert(km <= hl && hl <= r);
          if (km < hl) return {hc, hl};
          return dfs(hc, buffer.m_nodes[k].children[0], kl, km, next_lz);
        }
      })(SM::e(), this->m_root, 0, this->capacity(), FM::e()).second;
    }
  };
}

Back to top page