Sparse segment tree with lazy propagation (tools/lazy_sparse_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/lazy_sparse_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

(1) lazy_sparse_segtree<SM, FM, mapping> a(long long l_star, long long r_star);
(2) lazy_sparse_segtree<SM, FM, mapping> a(long long l_star, long long r_star, S x);

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).

• (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.

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))$
• $-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

• None

Time Complexity

• $O(1)$

upper_bound

long long a.upper_bound();

It returns $r^\ast$.

Constraints

• None

Time Complexity

• $O(1)$

set

void a.set(long long p, S x);

It assigns $x$ to $a_p$.

Constraints

• $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

• $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

• $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

• None

Time Complexity

• $O(1)$

apply

(1) void a.apply(long long p, F f);
(2) void a.apply(long long l, long long r, F f);

• (1)
  • It assigns $\mathrm{mapping}(f, a_p)$ to $a_p$.
• (2)
  • It assigns $\mathrm{mapping}(f, a_i)$ to $a_i$ for all $i$ such that $l \leq i < r$.

Constraints

• (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))$

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

• 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

• 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)
• Dummy monoid (tools/nop_monoid.hpp)

Required by

• Dual sparse segment tree (tools/dual_sparse_segtree.hpp)
• Sparse segment tree (tools/sparse_segtree.hpp)

Verified with

• tests/dual_sparse_segtree.test.cpp
• tests/lazy_sparse_segtree/binary_search.test.cpp
• tests/lazy_sparse_segtree/prod_and_apply.test.cpp
• tests/sparse_segtree.test.cpp

Code

#ifndef TOOLS_LAZY_SPARSE_SEGTREE_HPP
#define TOOLS_LAZY_SPARSE_SEGTREE_HPP

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

namespace tools {
  template <typename SM, typename FM, auto mapping>
  class lazy_sparse_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)");

    template <typename T>
    static constexpr bool has_data = !::std::is_same_v<T, ::tools::nop_monoid>;
    template <typename T>
    static constexpr bool has_lazy = !::std::is_same_v<T, ::tools::nop_monoid>;

    struct regular_node {
      S data;
      ::std::array<int, 2> children;
    };
    struct dual_node {
      F lazy;
      ::std::array<int, 2> children;
    };
    struct lazy_node {
      S data;
      F lazy;
      ::std::array<int, 2> children;
    };
    using node = ::std::conditional_t<has_data<SM>, ::std::conditional_t<has_lazy<FM>, lazy_node, regular_node>, dual_node>;

    ::std::vector<node> m_nodes;
    long long m_offset;
    long long m_size;
    int m_height;
    int m_root;

    long long capacity() const {
      return 1LL << this->m_height;
    }
    bool is_mutable(const int k) const {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      return this->m_height < k;
    }
    void make_mutable() {
      if (this->is_mutable(this->m_root)) return;
      this->m_nodes.push_back(this->m_nodes[this->m_root]);
      this->m_root = this->m_nodes.size() - 1;
    }
    void make_mutable(const int k, const int d) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(0 <= d && d < 2);
      assert(!this->is_leaf(k));
      if (this->is_mutable(this->m_nodes[k].children[d])) return;
      this->m_nodes.push_back(this->m_nodes[this->m_nodes[k].children[d]]);
      this->m_nodes[k].children[d] = this->m_nodes.size() - 1;
    }
    bool is_leaf(const int k) const {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      const auto& node = this->m_nodes[k];
      return node.children[0] < 0 && node.children[1] < 0;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void push(const int k) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      assert(!this->is_leaf(k));
      auto& node = this->m_nodes[k];
      this->all_apply(node.children[0], node.lazy);
      this->all_apply(node.children[1], node.lazy);
      node.lazy = FM::e();
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void all_apply(const int k, const F& f) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      auto& node = this->m_nodes[k];
      if constexpr (has_data<SM>) {
        node.data = mapping(f, node.data);
      }
      node.lazy = FM::op(f, node.lazy);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void update(const int k) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      assert(!this->is_leaf(k));
      auto& node = this->m_nodes[k];
      node.data = SM::op(this->m_nodes[node.children[0]].data, this->m_nodes[node.children[1]].data);
    }

  public:
    lazy_sparse_segtree() = default;
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star) : lazy_sparse_segtree(l_star, r_star, SM::e()) {
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star, const S& x) :
        m_offset(l_star), m_size(r_star - l_star), m_height(::tools::ceil_log2(::std::max(1LL, r_star - l_star))) {
      assert(l_star <= r_star);
      if constexpr (has_lazy<FM>) {
        this->m_nodes.push_back({x, FM::e(), {-1, -1}});
        for (int k = 1; k <= this->m_height; ++k) {
          this->m_nodes.push_back({SM::op(this->m_nodes.back().data, this->m_nodes.back().data), FM::e(), {k - 1, k - 1}});
        }
      } else {
        this->m_nodes.push_back({x, {-1, -1}});
        for (int k = 1; k <= this->m_height; ++k) {
          this->m_nodes.push_back({SM::op(this->m_nodes.back().data, this->m_nodes.back().data), {k - 1, k - 1}});
        }
      }
      this->m_root = this->m_height;
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star) :
        m_offset(l_star), m_size(r_star - l_star), m_height(::tools::ceil_log2(::std::max(1LL, r_star - l_star))) {
      assert(l_star <= r_star);
      this->m_nodes.push_back({FM::e(), {-1, -1}});
      for (int k = 1; k <= this->m_height; ++k) {
        this->m_nodes.push_back({FM::e(), {k - 1, k - 1}});
      }
      this->m_root = this->m_height;
    }

    long long lower_bound() const {
      return this->m_offset;
    }
    long long upper_bound() const {
      return this->m_offset + this->m_size;
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void set(long long p, const S& x) {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      p -= this->m_offset;

      this->make_mutable();
      ::tools::fix([&](auto&& dfs, const int h, const int k) -> void {
        assert(this->is_mutable(k));
        if (h > 0) {
          assert(!this->is_leaf(k));
          if constexpr (has_lazy<FM>) {
            this->make_mutable(k, 0);
            this->make_mutable(k, 1);
            this->push(k);
          } else {
            this->make_mutable(k, ((this->capacity() + p) >> (h - 1)) & 1);
          }
          dfs(h - 1, this->m_nodes[k].children[((this->capacity() + p) >> (h - 1)) & 1]);
          this->update(k);
        } else {
          assert(this->is_leaf(k));
          this->m_nodes[k].data = x;
        }
      })(this->m_height, this->m_root);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S get(const long long p) {
      return this->prod(p, p + 1);
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    F get(long long p) {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      p -= this->m_offset;

      this->make_mutable();
      return ::tools::fix([&](auto&& dfs, const int h, const int k) -> F {
        assert(this->is_mutable(k));
        if (h > 0) {
          assert(!this->is_leaf(k));
          this->make_mutable(k, 0);
          this->make_mutable(k, 1);
          this->push(k);
          return dfs(h - 1, this->m_nodes[k].children[((this->capacity() + p) >> (h - 1)) & 1]);
        } else {
          assert(this->is_leaf(k));
          return this->m_nodes[k].lazy;
        }
      })(this->m_height, this->m_root);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S prod(long long l, long long r) {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return SM::e();
      l -= this->m_offset;
      r -= this->m_offset;

      if constexpr (has_lazy<FM>) {
        this->make_mutable();
      }
      return ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return this->m_nodes[k].data;
        if constexpr (has_lazy<FM>) {
          this->make_mutable(k, 0);
          this->make_mutable(k, 1);
          this->push(k);
        }
        const auto km = ::std::midpoint(kl, kr);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(this->m_nodes[k].children[0], kl, km));
        if (km < r) res = SM::op(res, dfs(this->m_nodes[k].children[1], km, kr));
        return res;
      })(this->m_root, 0, this->capacity());
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S all_prod() const {
      return this->m_nodes[this->m_root].data;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const long long p, const F& f) {
      this->apply(p, p + 1, f);
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(long long l, long long r, const F& f) {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return;
      l -= this->m_offset;
      r -= this->m_offset;

      this->make_mutable();
      ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr) -> void {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          this->all_apply(k, f);
          return;
        }
        this->make_mutable(k, 0);
        this->make_mutable(k, 1);
        this->push(k);
        const auto km = ::std::midpoint(kl, kr);
        if (l < km) dfs(this->m_nodes[k].children[0], kl, km);
        if (km < r) dfs(this->m_nodes[k].children[1], km, kr);
        if constexpr (has_data<SM>) {
          this->update(k);
        }
      })(this->m_root, 0, this->capacity());
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    long long max_right(long long l, const G& g) {
      assert(this->lower_bound() <= l && l <= this->upper_bound());
      assert(g(SM::e()));
      if (l == this->upper_bound()) return l;
      l -= this->m_offset;

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

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

#endif

#line 1 "tools/lazy_sparse_segtree.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <functional>
#include <numeric>
#include <type_traits>
#include <utility>
#include <variant>
#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 1 "tools/nop_monoid.hpp"



#line 5 "tools/nop_monoid.hpp"

namespace tools {
  struct nop_monoid {
    using T = ::std::monostate;
    static T op(T, T) {
      return {};
    }
    static T e() {
      return {};
    }
  };
}


#line 16 "tools/lazy_sparse_segtree.hpp"

namespace tools {
  template <typename SM, typename FM, auto mapping>
  class lazy_sparse_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)");

    template <typename T>
    static constexpr bool has_data = !::std::is_same_v<T, ::tools::nop_monoid>;
    template <typename T>
    static constexpr bool has_lazy = !::std::is_same_v<T, ::tools::nop_monoid>;

    struct regular_node {
      S data;
      ::std::array<int, 2> children;
    };
    struct dual_node {
      F lazy;
      ::std::array<int, 2> children;
    };
    struct lazy_node {
      S data;
      F lazy;
      ::std::array<int, 2> children;
    };
    using node = ::std::conditional_t<has_data<SM>, ::std::conditional_t<has_lazy<FM>, lazy_node, regular_node>, dual_node>;

    ::std::vector<node> m_nodes;
    long long m_offset;
    long long m_size;
    int m_height;
    int m_root;

    long long capacity() const {
      return 1LL << this->m_height;
    }
    bool is_mutable(const int k) const {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      return this->m_height < k;
    }
    void make_mutable() {
      if (this->is_mutable(this->m_root)) return;
      this->m_nodes.push_back(this->m_nodes[this->m_root]);
      this->m_root = this->m_nodes.size() - 1;
    }
    void make_mutable(const int k, const int d) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(0 <= d && d < 2);
      assert(!this->is_leaf(k));
      if (this->is_mutable(this->m_nodes[k].children[d])) return;
      this->m_nodes.push_back(this->m_nodes[this->m_nodes[k].children[d]]);
      this->m_nodes[k].children[d] = this->m_nodes.size() - 1;
    }
    bool is_leaf(const int k) const {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      const auto& node = this->m_nodes[k];
      return node.children[0] < 0 && node.children[1] < 0;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void push(const int k) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      assert(!this->is_leaf(k));
      auto& node = this->m_nodes[k];
      this->all_apply(node.children[0], node.lazy);
      this->all_apply(node.children[1], node.lazy);
      node.lazy = FM::e();
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void all_apply(const int k, const F& f) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      auto& node = this->m_nodes[k];
      if constexpr (has_data<SM>) {
        node.data = mapping(f, node.data);
      }
      node.lazy = FM::op(f, node.lazy);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void update(const int k) {
      assert(0 <= k && ::std::cmp_less(k, this->m_nodes.size()));
      assert(this->is_mutable(k));
      assert(!this->is_leaf(k));
      auto& node = this->m_nodes[k];
      node.data = SM::op(this->m_nodes[node.children[0]].data, this->m_nodes[node.children[1]].data);
    }

  public:
    lazy_sparse_segtree() = default;
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star) : lazy_sparse_segtree(l_star, r_star, SM::e()) {
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star, const S& x) :
        m_offset(l_star), m_size(r_star - l_star), m_height(::tools::ceil_log2(::std::max(1LL, r_star - l_star))) {
      assert(l_star <= r_star);
      if constexpr (has_lazy<FM>) {
        this->m_nodes.push_back({x, FM::e(), {-1, -1}});
        for (int k = 1; k <= this->m_height; ++k) {
          this->m_nodes.push_back({SM::op(this->m_nodes.back().data, this->m_nodes.back().data), FM::e(), {k - 1, k - 1}});
        }
      } else {
        this->m_nodes.push_back({x, {-1, -1}});
        for (int k = 1; k <= this->m_height; ++k) {
          this->m_nodes.push_back({SM::op(this->m_nodes.back().data, this->m_nodes.back().data), {k - 1, k - 1}});
        }
      }
      this->m_root = this->m_height;
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    lazy_sparse_segtree(const long long l_star, const long long r_star) :
        m_offset(l_star), m_size(r_star - l_star), m_height(::tools::ceil_log2(::std::max(1LL, r_star - l_star))) {
      assert(l_star <= r_star);
      this->m_nodes.push_back({FM::e(), {-1, -1}});
      for (int k = 1; k <= this->m_height; ++k) {
        this->m_nodes.push_back({FM::e(), {k - 1, k - 1}});
      }
      this->m_root = this->m_height;
    }

    long long lower_bound() const {
      return this->m_offset;
    }
    long long upper_bound() const {
      return this->m_offset + this->m_size;
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void set(long long p, const S& x) {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      p -= this->m_offset;

      this->make_mutable();
      ::tools::fix([&](auto&& dfs, const int h, const int k) -> void {
        assert(this->is_mutable(k));
        if (h > 0) {
          assert(!this->is_leaf(k));
          if constexpr (has_lazy<FM>) {
            this->make_mutable(k, 0);
            this->make_mutable(k, 1);
            this->push(k);
          } else {
            this->make_mutable(k, ((this->capacity() + p) >> (h - 1)) & 1);
          }
          dfs(h - 1, this->m_nodes[k].children[((this->capacity() + p) >> (h - 1)) & 1]);
          this->update(k);
        } else {
          assert(this->is_leaf(k));
          this->m_nodes[k].data = x;
        }
      })(this->m_height, this->m_root);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S get(const long long p) {
      return this->prod(p, p + 1);
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    F get(long long p) {
      assert(this->lower_bound() <= p && p < this->upper_bound());
      p -= this->m_offset;

      this->make_mutable();
      return ::tools::fix([&](auto&& dfs, const int h, const int k) -> F {
        assert(this->is_mutable(k));
        if (h > 0) {
          assert(!this->is_leaf(k));
          this->make_mutable(k, 0);
          this->make_mutable(k, 1);
          this->push(k);
          return dfs(h - 1, this->m_nodes[k].children[((this->capacity() + p) >> (h - 1)) & 1]);
        } else {
          assert(this->is_leaf(k));
          return this->m_nodes[k].lazy;
        }
      })(this->m_height, this->m_root);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S prod(long long l, long long r) {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return SM::e();
      l -= this->m_offset;
      r -= this->m_offset;

      if constexpr (has_lazy<FM>) {
        this->make_mutable();
      }
      return ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return this->m_nodes[k].data;
        if constexpr (has_lazy<FM>) {
          this->make_mutable(k, 0);
          this->make_mutable(k, 1);
          this->push(k);
        }
        const auto km = ::std::midpoint(kl, kr);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(this->m_nodes[k].children[0], kl, km));
        if (km < r) res = SM::op(res, dfs(this->m_nodes[k].children[1], km, kr));
        return res;
      })(this->m_root, 0, this->capacity());
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S all_prod() const {
      return this->m_nodes[this->m_root].data;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const long long p, const F& f) {
      this->apply(p, p + 1, f);
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(long long l, long long r, const F& f) {
      assert(this->lower_bound() <= l && l <= r && r <= this->upper_bound());
      if (l == r) return;
      l -= this->m_offset;
      r -= this->m_offset;

      this->make_mutable();
      ::tools::fix([&](auto&& dfs, const int k, const long long kl, const long long kr) -> void {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          this->all_apply(k, f);
          return;
        }
        this->make_mutable(k, 0);
        this->make_mutable(k, 1);
        this->push(k);
        const auto km = ::std::midpoint(kl, kr);
        if (l < km) dfs(this->m_nodes[k].children[0], kl, km);
        if (km < r) dfs(this->m_nodes[k].children[1], km, kr);
        if constexpr (has_data<SM>) {
          this->update(k);
        }
      })(this->m_root, 0, this->capacity());
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    long long max_right(long long l, const G& g) {
      assert(this->lower_bound() <= l && l <= this->upper_bound());
      assert(g(SM::e()));
      if (l == this->upper_bound()) return l;
      l -= this->m_offset;

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

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

Back to top page