Segment tree with lazy propagation (tools/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/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)$.

Note

This class is just a sample implementation to serve as a basis for other extensions of segment trees with lazy propagation. For practical purposes, use atcoder::lazy_segtree.

License

• CC0

Author

• anqooqie

Constructor

(1) lazy_segtree<SM, FM, mapping> a(int n);
(2) lazy_segtree<SM, FM, mapping> a(std::ranges::range v);

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 of length n. All the elements are initialized to e().
• (2)
  • It creates an array a of length n = v.size(), initialized to v.

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))$
• $n \geq 0$

Time Complexity

• $O(n)$

size

int a.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

set

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

a[p] = x

Constraints

• $0 \leq p < n$

Time Complexity

• $O(\log n)$

get

S a.get(int p);

It returns a[p].

Constraints

• $0 \leq p < n$

Time Complexity

• $O(\log n)$

prod

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

It returns op(a[l], ..., a[r - 1]), assuming the properties of the monoid. It returns e() if $l = r$.

Constraints

• $0 \leq l \leq r \leq n$

Time Complexity

• $O(\log n)$

all_prod

S a.all_prod();

It returns op(a[0], ..., a[n - 1]), assuming the properties of the monoid. It returns e() if $n = 0$.

Constraints

• None

Time Complexity

• $O(1)$

apply

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

• (1)
  • It applies a[p] = f(a[p]).
• (2)
  • It applies a[i] = f(a[i]) for all i = l..r-1.

Constraints

• (1)
  • $0 \leq p < n$
• (2)
  • $0 \leq l \leq r \leq n$

Time Complexity

• $O(\log n)$

max_right

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

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

• r = l or g(op(a[l], a[l + 1], ..., a[r - 1])) = true
• r = a.size() or g(op(a[l], a[l + 1], ..., a[r])) = false

If g is monotone, this is the maximum r that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

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(e()) = true
• $0 \leq l \leq n$

Time Complexity

• $O(\log n)$

min_left

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

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

• l = r or g(op(a[l], a[l + 1], ..., a[r - 1])) = true
• l = 0 or g(op(a[l - 1], a[l], ..., a[r - 1])) = false

If g is monotone, this is the minimum l that satisfies g(op(a[l], a[l + 1], ..., a[r - 1])) = true.

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(e()) = true
• $0 \leq r \leq n$

Time Complexity

• $O(\log n)$

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)

Verified with

• tests/lazy_segtree/dual_segtree.test.cpp
• tests/lazy_segtree/lazy_segtree/binary_search.test.cpp
• tests/lazy_segtree/lazy_segtree/prod_and_apply.test.cpp
• tests/lazy_segtree/segtree.test.cpp

Code

#ifndef TOOLS_LAZY_SEGTREE_HPP
#define TOOLS_LAZY_SEGTREE_HPP

#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <ranges>
#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_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>;

    int m_size;
    int m_height;
    ::std::vector<S> m_data;
    ::std::vector<F> m_lazy;

    int capacity() const {
      return 1 << this->m_height;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void push(const int k) {
      assert(0 < k && k < this->capacity());
      this->all_apply(2 * k, this->m_lazy[k]);
      this->all_apply(2 * k + 1, this->m_lazy[k]);
      this->m_lazy[k] = FM::e();
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void all_apply(const int k, const F& f) {
      assert(0 < k && k < 2 * this->capacity());
      if constexpr (has_data<SM>) {
        this->m_data[k] = mapping(f, this->m_data[k]);
        if (k < this->capacity()) this->m_lazy[k] = FM::op(f, this->m_lazy[k]);
      } else {
        this->m_lazy[k] = FM::op(f, this->m_lazy[k]);
      }
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void update(const int k) {
      assert(0 < k && this->capacity());
      this->m_data[k] = SM::op(this->m_data[2 * k], this->m_data[2 * k + 1]);
    }

  public:
    lazy_segtree() = default;
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    explicit lazy_segtree(const int n) : lazy_segtree(::std::vector<S>(n, SM::e())) {
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    explicit lazy_segtree(const int n) : m_size(n), m_height(::tools::ceil_log2(::std::max(1, n))) {
      this->m_lazy.assign(2 * this->capacity(), FM::e());
    }
    template <::std::ranges::range R, typename SFINAE = SM> requires (has_data<SFINAE>)
    explicit lazy_segtree(R&& r) : m_data(::std::ranges::begin(r), ::std::ranges::end(r)) {
      this->m_size = this->m_data.size();
      this->m_height = ::tools::ceil_log2(::std::max(1, this->m_size));
      this->m_data.reserve(2 * this->capacity());
      this->m_data.insert(this->m_data.begin(), this->capacity(), SM::e());
      this->m_data.resize(2 * this->capacity(), SM::e());
      for (auto k = this->capacity() - 1; k > 0; --k) this->update(k);
      if constexpr (has_lazy<FM>) {
        this->m_lazy.assign(this->capacity(), FM::e());
      }
    }

    int size() const {
      return this->m_size;
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void set(const int p, const S& x) {
      assert(0 <= p && p < this->m_size);
      ::tools::fix([&](auto&& dfs, const int h, const int k) -> void {
        if (h > 0) {
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          dfs(h - 1, (this->capacity() + p) >> (h - 1));
          this->update(k);
        } else {
          this->m_data[this->capacity() + p] = x;
        }
      })(this->m_height, 1);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S get(const int p) {
      return this->prod(p, p + 1);
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    F get(const int p) {
      assert(0 <= p && p < this->m_size);
      return ::tools::fix([&](auto&& dfs, const int h, const int k) -> F {
        if (h > 0) {
          this->push(k);
          return dfs(h - 1, (this->capacity() + p) >> (h - 1));
        } else {
          return this->m_lazy[this->capacity() + p];
        }
      })(this->m_height, 1);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S prod(const int l, const int r) {
      assert(0 <= l && l <= r && r <= this->m_size);
      if (l == r) return SM::e();
      return ::tools::fix([&](auto&& dfs, const int k, const int kl, const int kr) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return this->m_data[k];
        if constexpr (has_lazy<FM>) {
          this->push(k);
        }
        const auto km = ::std::midpoint(kl, kr);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(k << 1, kl, km));
        if (km < r) res = SM::op(res, dfs((k << 1) + 1, km, kr));
        return res;
      })(1, 0, this->capacity());
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S all_prod() const {
      return this->m_data[1];
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const int p, const F& f) {
      this->apply(p, p + 1, f);
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const int l, const int r, const F& f) {
      assert(0 <= l && l <= r && r <= this->m_size);
      if (l == r) return;
      ::tools::fix([&](auto&& dfs, const int k, const int kl, const int kr) -> void {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          this->all_apply(k, f);
          return;
        }
        this->push(k);
        const auto km = ::std::midpoint(kl, kr);
        if (l < km) dfs(k << 1, kl, km);
        if (km < r) dfs((k << 1) + 1, km, kr);
        if constexpr (has_data<SM>) {
          this->update(k);
        }
      })(1, 0, this->capacity());
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    int max_right(const int l, const G& g) {
      assert(0 <= l && l <= this->m_size);
      assert(g(SM::e()));
      if (l == this->m_size) return l;
      return ::std::min(::tools::fix([&](auto&& dfs, const S& c, const int k, const int kl, const int kr) -> ::std::pair<S, int> {
        assert(kl < kr);
        if (kl < l) {
          assert(kl < l && l < kr);
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          if (l < km) {
            const auto [hc, hr] = dfs(c, k << 1, kl, km);
            assert(l <= hr && hr <= km);
            if (hr < km) return {hc, hr};
            return dfs(hc, (k << 1) + 1, km, kr);
          } else {
            return dfs(c, (k << 1) + 1, km, kr);
          }
        } else {
          if (const auto wc = SM::op(c, this->m_data[k]); g(wc)) return {wc, kr};
          if (kr - kl == 1) return {c, kl};
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          const auto [hc, hr] = dfs(c, k << 1, kl, km);
          assert(l <= hr && hr <= km);
          if (hr < km) return {hc, hr};
          return dfs(hc, (k << 1) + 1, km, kr);
        }
      })(SM::e(), 1, 0, this->capacity()).second, this->m_size);
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    int min_left(const int r, const G& g) {
      assert(0 <= r && r <= this->m_size);
      assert(g(SM::e()));
      if (r == 0) return r;
      return ::tools::fix([&](auto&& dfs, const S& c, const int k, const int kl, const int kr) -> ::std::pair<S, int> {
        assert(kl < kr);
        if (r < kr) {
          assert(kl < r && r < kr);
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          if (km < r) {
            const auto [hc, hl] = dfs(c, (k << 1) + 1, km, kr);
            assert(km <= hl && hl <= r);
            if (km < hl) return {hc, hl};
            return dfs(hc, k << 1, kl, km);
          } else {
            return dfs(c, k << 1, kl, km);
          }
        } else {
          if (const auto wc = SM::op(this->m_data[k], c); g(wc)) return {wc, kl};
          if (kr - kl == 1) return {c, kr};
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          const auto [hc, hl] = dfs(c, (k << 1) + 1, km, kr);
          assert(km <= hl && hl <= r);
          if (km < hl) return {hc, hl};
          return dfs(hc, k << 1, kl, km);
        }
      })(SM::e(), 1, 0, this->capacity()).second;
    }
  };
}

#endif

#line 1 "tools/lazy_segtree.hpp"



#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <ranges>
#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_segtree.hpp"

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

    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>;

    int m_size;
    int m_height;
    ::std::vector<S> m_data;
    ::std::vector<F> m_lazy;

    int capacity() const {
      return 1 << this->m_height;
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void push(const int k) {
      assert(0 < k && k < this->capacity());
      this->all_apply(2 * k, this->m_lazy[k]);
      this->all_apply(2 * k + 1, this->m_lazy[k]);
      this->m_lazy[k] = FM::e();
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void all_apply(const int k, const F& f) {
      assert(0 < k && k < 2 * this->capacity());
      if constexpr (has_data<SM>) {
        this->m_data[k] = mapping(f, this->m_data[k]);
        if (k < this->capacity()) this->m_lazy[k] = FM::op(f, this->m_lazy[k]);
      } else {
        this->m_lazy[k] = FM::op(f, this->m_lazy[k]);
      }
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void update(const int k) {
      assert(0 < k && this->capacity());
      this->m_data[k] = SM::op(this->m_data[2 * k], this->m_data[2 * k + 1]);
    }

  public:
    lazy_segtree() = default;
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    explicit lazy_segtree(const int n) : lazy_segtree(::std::vector<S>(n, SM::e())) {
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    explicit lazy_segtree(const int n) : m_size(n), m_height(::tools::ceil_log2(::std::max(1, n))) {
      this->m_lazy.assign(2 * this->capacity(), FM::e());
    }
    template <::std::ranges::range R, typename SFINAE = SM> requires (has_data<SFINAE>)
    explicit lazy_segtree(R&& r) : m_data(::std::ranges::begin(r), ::std::ranges::end(r)) {
      this->m_size = this->m_data.size();
      this->m_height = ::tools::ceil_log2(::std::max(1, this->m_size));
      this->m_data.reserve(2 * this->capacity());
      this->m_data.insert(this->m_data.begin(), this->capacity(), SM::e());
      this->m_data.resize(2 * this->capacity(), SM::e());
      for (auto k = this->capacity() - 1; k > 0; --k) this->update(k);
      if constexpr (has_lazy<FM>) {
        this->m_lazy.assign(this->capacity(), FM::e());
      }
    }

    int size() const {
      return this->m_size;
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    void set(const int p, const S& x) {
      assert(0 <= p && p < this->m_size);
      ::tools::fix([&](auto&& dfs, const int h, const int k) -> void {
        if (h > 0) {
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          dfs(h - 1, (this->capacity() + p) >> (h - 1));
          this->update(k);
        } else {
          this->m_data[this->capacity() + p] = x;
        }
      })(this->m_height, 1);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S get(const int p) {
      return this->prod(p, p + 1);
    }
    template <typename SFINAE = SM> requires (!has_data<SFINAE>)
    F get(const int p) {
      assert(0 <= p && p < this->m_size);
      return ::tools::fix([&](auto&& dfs, const int h, const int k) -> F {
        if (h > 0) {
          this->push(k);
          return dfs(h - 1, (this->capacity() + p) >> (h - 1));
        } else {
          return this->m_lazy[this->capacity() + p];
        }
      })(this->m_height, 1);
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S prod(const int l, const int r) {
      assert(0 <= l && l <= r && r <= this->m_size);
      if (l == r) return SM::e();
      return ::tools::fix([&](auto&& dfs, const int k, const int kl, const int kr) -> S {
        assert(kl < kr);
        if (l <= kl && kr <= r) return this->m_data[k];
        if constexpr (has_lazy<FM>) {
          this->push(k);
        }
        const auto km = ::std::midpoint(kl, kr);
        S res = SM::e();
        if (l < km) res = SM::op(res, dfs(k << 1, kl, km));
        if (km < r) res = SM::op(res, dfs((k << 1) + 1, km, kr));
        return res;
      })(1, 0, this->capacity());
    }
    template <typename SFINAE = SM> requires (has_data<SFINAE>)
    S all_prod() const {
      return this->m_data[1];
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const int p, const F& f) {
      this->apply(p, p + 1, f);
    }
    template <typename SFINAE = FM> requires (has_lazy<SFINAE>)
    void apply(const int l, const int r, const F& f) {
      assert(0 <= l && l <= r && r <= this->m_size);
      if (l == r) return;
      ::tools::fix([&](auto&& dfs, const int k, const int kl, const int kr) -> void {
        assert(kl < kr);
        if (l <= kl && kr <= r) {
          this->all_apply(k, f);
          return;
        }
        this->push(k);
        const auto km = ::std::midpoint(kl, kr);
        if (l < km) dfs(k << 1, kl, km);
        if (km < r) dfs((k << 1) + 1, km, kr);
        if constexpr (has_data<SM>) {
          this->update(k);
        }
      })(1, 0, this->capacity());
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    int max_right(const int l, const G& g) {
      assert(0 <= l && l <= this->m_size);
      assert(g(SM::e()));
      if (l == this->m_size) return l;
      return ::std::min(::tools::fix([&](auto&& dfs, const S& c, const int k, const int kl, const int kr) -> ::std::pair<S, int> {
        assert(kl < kr);
        if (kl < l) {
          assert(kl < l && l < kr);
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          if (l < km) {
            const auto [hc, hr] = dfs(c, k << 1, kl, km);
            assert(l <= hr && hr <= km);
            if (hr < km) return {hc, hr};
            return dfs(hc, (k << 1) + 1, km, kr);
          } else {
            return dfs(c, (k << 1) + 1, km, kr);
          }
        } else {
          if (const auto wc = SM::op(c, this->m_data[k]); g(wc)) return {wc, kr};
          if (kr - kl == 1) return {c, kl};
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          const auto [hc, hr] = dfs(c, k << 1, kl, km);
          assert(l <= hr && hr <= km);
          if (hr < km) return {hc, hr};
          return dfs(hc, (k << 1) + 1, km, kr);
        }
      })(SM::e(), 1, 0, this->capacity()).second, this->m_size);
    }
    template <typename G, typename SFINAE = SM> requires (has_data<SFINAE>)
    int min_left(const int r, const G& g) {
      assert(0 <= r && r <= this->m_size);
      assert(g(SM::e()));
      if (r == 0) return r;
      return ::tools::fix([&](auto&& dfs, const S& c, const int k, const int kl, const int kr) -> ::std::pair<S, int> {
        assert(kl < kr);
        if (r < kr) {
          assert(kl < r && r < kr);
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          if (km < r) {
            const auto [hc, hl] = dfs(c, (k << 1) + 1, km, kr);
            assert(km <= hl && hl <= r);
            if (km < hl) return {hc, hl};
            return dfs(hc, k << 1, kl, km);
          } else {
            return dfs(c, k << 1, kl, km);
          }
        } else {
          if (const auto wc = SM::op(this->m_data[k], c); g(wc)) return {wc, kl};
          if (kr - kl == 1) return {c, kr};
          if constexpr (has_lazy<FM>) {
            this->push(k);
          }
          const auto km = ::std::midpoint(kl, kr);
          const auto [hc, hl] = dfs(c, (k << 1) + 1, km, kr);
          assert(km <= hl && hl <= r);
          if (km < hl) return {hc, hl};
          return dfs(hc, k << 1, kl, km);
        }
      })(SM::e(), 1, 0, this->capacity()).second;
    }
  };
}

Back to top page