algorithm/DataStructure/SegmentTree/dynamic_segment_tree.hpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Include: #include "algorithm/DataStructure/SegmentTree/dynamic_segment_tree.hpp"

Depends on

algorithm/Math/Algebra/algebra.hpp

Verified with

Code

#ifndef ALGORITHM_DYNAMIC_SEGMENT_TREE_HPP
#define ALGORITHM_DYNAMIC_SEGMENT_TREE_HPP 1

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

#include "../../Math/Algebra/algebra.hpp"

namespace algorithm {

namespace dynamic_segment_tree {

template <class Monoid>
class DynamicSegmentTree {
public:
    using monoid_type = Monoid;
    using value_type = monoid_type::value_type;
    using size_type = std::size_t;

private:
    struct Node;
    using node_pointer = std::unique_ptr<Node>;

    struct Node {
        size_type index;
        monoid_type value;
        monoid_type product;
        node_pointer left, right;

        explicit Node(size_type index, const monoid_type &value) : index(index), value(value), product(value), left(nullptr), right(nullptr) {}
    };

    size_type m_sz;       // m_sz:=(要素数).
    node_pointer m_root;  // m_root:=(根のポインタ).

    void update(const node_pointer &p) const {
        const monoid_type &lhs = (p->left ? p->left->product : monoid_type::one());
        const monoid_type &rhs = (p->right ? p->right->product : monoid_type::one());
        p->product = lhs * p->value * rhs;
    }
    void set(node_pointer &p, size_type k, monoid_type a, size_type l, size_type r) {
        if(!p) {
            p = std::make_unique<Node>(k, a);
            return;
        }
        if(p->index == k) {
            p->value = a;
            update(p);
            return;
        }
        size_type mid = l + (r - l) / 2;
        if(k < mid) {
            if(p->index < k) std::swap(k, p->index), std::swap(a, p->value);
            set(p->left, k, a, l, mid);
        } else {
            if(k < p->index) std::swap(k, p->index), std::swap(a, p->value);
            set(p->right, k, a, mid, r);
        }
        update(p);
    }
    monoid_type prod(const node_pointer &p, size_type k, size_type l, size_type r) const {
        if(!p) return monoid_type::one();
        if(p->index == k) return p->value;
        size_type mid = l + (r - l) / 2;
        return (k < mid ? prod(p->left, k, l, mid) : prod(p->right, k, mid, r));
    }
    monoid_type prod(const node_pointer &p, size_type l, size_type r, size_type ll, size_type rr) const {
        if(!p or r <= ll or rr <= l) return monoid_type::one();
        if(l <= ll and rr <= r) return p->product;
        size_type mid = ll + (rr - ll) / 2;
        return prod(p->left, l, r, ll, mid) * (l <= p->index and p->index < r ? p->value : monoid_type::one()) * prod(p->right, l, r, mid, rr);
    }
    template <typename Pred>
    size_type most_right(const node_pointer &p, size_type l, Pred pred, size_type ll, size_type rr, monoid_type &product) const {
        if(!p or rr <= l) return rr;
        if(l <= ll and pred((product * p->product).value())) {
            product = product * p->product;
            return rr;
        }
        size_type mid = ll + (rr - ll) / 2;
        size_type itr = most_right(p->left, l, pred, ll, mid, product);
        if(itr < mid) return itr;
        if(l <= p->index) {
            product = product * p->value;
            if(!pred(product.value())) return p->index;
        }
        return most_right(p->right, l, pred, mid, rr, product);
    }
    template <typename Pred>
    size_type most_left(const node_pointer &p, size_type r, Pred pred, size_type ll, size_type rr, monoid_type &product) const {
        if(!p or r <= ll) return ll;
        if(rr <= r and pred((p->product * product).value())) {
            product = p->product * product;
            return ll;
        }
        size_type mid = ll + (rr - ll) / 2;
        size_type itr = most_left(p->right, r, pred, mid, rr, product);
        if(mid < itr) return itr;
        if(p->index < r) {
            product = p->value * product;
            if(!pred(product.value())) return p->index + 1;
        }
        return most_left(p->left, r, pred, ll, mid, product);
    }
    void reset(node_pointer &p, size_type l, size_type r, size_type ll, size_type rr) {
        if(!p or r <= ll or rr <= l) return;
        if(l <= ll and rr <= r) {
            p.reset();
            return;
        }
        size_type mid = ll + (rr - ll) / 2;
        reset(p->left, l, r, ll, mid);
        reset(p->right, l, r, mid, rr);
        if(l <= p->index and p->index < r) {
            if(!p->left and !p->right) {
                p.reset();
                return;
            }
            p->value = monoid_type::one();
        }
        update(p);
    }
    void print(std::ostream &os, const node_pointer &p, bool &first) const {
        if(!p) return;
        print(os, p->left, first);
        os << (first ? "{" : " {") << p->index << ", " << p->value << "}";
        first = false;
        print(os, p->right, first);
    }

public:
    DynamicSegmentTree() : DynamicSegmentTree(std::numeric_limits<size_type>::max()) {};
    explicit DynamicSegmentTree(size_type n) : m_sz(n), m_root(nullptr) {}

    // 要素数を取得する．
    size_type size() const { return m_sz; }
    // k番目の要素をaに置き換える．O(log N).
    void set(size_type k, const value_type &a) { set(k, monoid_type(a)); }
    void set(size_type k, const monoid_type &a) {
        assert(k < size());
        set(m_root, k, a, 0, m_sz);
    }
    // k番目の要素を取得する．O(log N).
    value_type prod(size_type k) const {
        assert(k < size());
        return prod(m_root, k, 0, m_sz).value();
    }
    // 区間[l,r)の要素の総積を求める．O(log N).
    value_type prod(size_type l, size_type r) const {
        assert(l <= r and r <= size());
        return prod(m_root, l, r, 0, m_sz).value();
    }
    // 区間全体の要素の総積を取得する．O(1).
    value_type prod_all() const { return (m_root ? m_root->product : monoid_type::one()).value(); }
    // pred(prod(l,r))==true となる区間の最右位値rを二分探索する．
    // ただし，区間[l,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    size_type most_right(size_type l) const {
        return most_right(l, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    size_type most_right(size_type l, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(l <= size());
        assert(pred(monoid_type::one().value()));
        monoid_type &&product = monoid_type::one();
        return most_right(m_root, l, pred, 0, m_sz, product);
    }
    // pred(prod(l,r))==true となる区間の最左位値lを二分探索する．
    // ただし，区間[0,r)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    size_type most_left(int r) const {
        return most_left(r, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    size_type most_left(size_type r, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(r <= size());
        assert(pred(monoid_type::one().value()));
        value_type &&product = monoid_type::one();
        return most_left(m_root, r, pred, 0, m_sz, product);
    }
    void reset(size_type k) { reset(m_root, k, k + 1, 0, m_sz); }
    void reset(size_type l, size_type r) {
        assert(l <= r and r <= size());
        reset(m_root, l, r, 0, m_sz);
    }
    void reset() { m_root.reset(); }

    friend std::ostream &operator<<(std::ostream &os, const DynamicSegmentTree &rhs) {
        os << "[";
        bool first = true;
        rhs.print(os, rhs.m_root, first);
        return os << "]";
    }
};

template <typename S>
using range_minimum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::minimum<S>>;

template <typename S>
using range_maximum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::maximum<S>>;

template <typename S>
using range_sum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::addition<S>>;

}  // namespace dynamic_segment_tree

}  // namespace algorithm

#endif

#line 1 "algorithm/DataStructure/SegmentTree/dynamic_segment_tree.hpp"



#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

#line 1 "algorithm/Math/Algebra/algebra.hpp"



#line 7 "algorithm/Math/Algebra/algebra.hpp"
#include <numeric>
#line 10 "algorithm/Math/Algebra/algebra.hpp"

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.val == rhs.val; }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.val; }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

    using base_type = Set<S>;

public:
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.val, rhs.val)); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

    using base_type = Semigroup<S, op>;

public:
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.val, rhs.val)); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

    using base_type = Monoid<S, op, e>;

public:
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.val, rhs.val)); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                // return identity element.
    constexpr Group inv() const { return Group(inverse(this->val)); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

    using base_type = Monoid<F, compose, id>;

public:
    using value_type = typename base_type::value_type;
    using acted_value_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.val, rhs.val)); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_value_type act(const acted_value_type &x) const { return mapping(this->val, x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_value_type>, S>::value);
        return S(mapping(this->val, x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace uoperator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace uoperator

namespace boperator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace boperator

namespace monoid {

template <typename S>
using minimum = Monoid<S, boperator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, boperator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, boperator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, boperator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, boperator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, boperator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, boperator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, boperator::plus<S>, element::zero<S>, uoperator::negate<S>>;

template <typename S>
using bit_xor = Group<S, boperator::bit_xor<S>, element::zero<S>, uoperator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, boperator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, boperator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, boperator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, boperator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<F, boperator::plus<F>, element::zero<F>, X, boperator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm


#line 13 "algorithm/DataStructure/SegmentTree/dynamic_segment_tree.hpp"

namespace algorithm {

namespace dynamic_segment_tree {

template <class Monoid>
class DynamicSegmentTree {
public:
    using monoid_type = Monoid;
    using value_type = monoid_type::value_type;
    using size_type = std::size_t;

private:
    struct Node;
    using node_pointer = std::unique_ptr<Node>;

    struct Node {
        size_type index;
        monoid_type value;
        monoid_type product;
        node_pointer left, right;

        explicit Node(size_type index, const monoid_type &value) : index(index), value(value), product(value), left(nullptr), right(nullptr) {}
    };

    size_type m_sz;       // m_sz:=(要素数).
    node_pointer m_root;  // m_root:=(根のポインタ).

    void update(const node_pointer &p) const {
        const monoid_type &lhs = (p->left ? p->left->product : monoid_type::one());
        const monoid_type &rhs = (p->right ? p->right->product : monoid_type::one());
        p->product = lhs * p->value * rhs;
    }
    void set(node_pointer &p, size_type k, monoid_type a, size_type l, size_type r) {
        if(!p) {
            p = std::make_unique<Node>(k, a);
            return;
        }
        if(p->index == k) {
            p->value = a;
            update(p);
            return;
        }
        size_type mid = l + (r - l) / 2;
        if(k < mid) {
            if(p->index < k) std::swap(k, p->index), std::swap(a, p->value);
            set(p->left, k, a, l, mid);
        } else {
            if(k < p->index) std::swap(k, p->index), std::swap(a, p->value);
            set(p->right, k, a, mid, r);
        }
        update(p);
    }
    monoid_type prod(const node_pointer &p, size_type k, size_type l, size_type r) const {
        if(!p) return monoid_type::one();
        if(p->index == k) return p->value;
        size_type mid = l + (r - l) / 2;
        return (k < mid ? prod(p->left, k, l, mid) : prod(p->right, k, mid, r));
    }
    monoid_type prod(const node_pointer &p, size_type l, size_type r, size_type ll, size_type rr) const {
        if(!p or r <= ll or rr <= l) return monoid_type::one();
        if(l <= ll and rr <= r) return p->product;
        size_type mid = ll + (rr - ll) / 2;
        return prod(p->left, l, r, ll, mid) * (l <= p->index and p->index < r ? p->value : monoid_type::one()) * prod(p->right, l, r, mid, rr);
    }
    template <typename Pred>
    size_type most_right(const node_pointer &p, size_type l, Pred pred, size_type ll, size_type rr, monoid_type &product) const {
        if(!p or rr <= l) return rr;
        if(l <= ll and pred((product * p->product).value())) {
            product = product * p->product;
            return rr;
        }
        size_type mid = ll + (rr - ll) / 2;
        size_type itr = most_right(p->left, l, pred, ll, mid, product);
        if(itr < mid) return itr;
        if(l <= p->index) {
            product = product * p->value;
            if(!pred(product.value())) return p->index;
        }
        return most_right(p->right, l, pred, mid, rr, product);
    }
    template <typename Pred>
    size_type most_left(const node_pointer &p, size_type r, Pred pred, size_type ll, size_type rr, monoid_type &product) const {
        if(!p or r <= ll) return ll;
        if(rr <= r and pred((p->product * product).value())) {
            product = p->product * product;
            return ll;
        }
        size_type mid = ll + (rr - ll) / 2;
        size_type itr = most_left(p->right, r, pred, mid, rr, product);
        if(mid < itr) return itr;
        if(p->index < r) {
            product = p->value * product;
            if(!pred(product.value())) return p->index + 1;
        }
        return most_left(p->left, r, pred, ll, mid, product);
    }
    void reset(node_pointer &p, size_type l, size_type r, size_type ll, size_type rr) {
        if(!p or r <= ll or rr <= l) return;
        if(l <= ll and rr <= r) {
            p.reset();
            return;
        }
        size_type mid = ll + (rr - ll) / 2;
        reset(p->left, l, r, ll, mid);
        reset(p->right, l, r, mid, rr);
        if(l <= p->index and p->index < r) {
            if(!p->left and !p->right) {
                p.reset();
                return;
            }
            p->value = monoid_type::one();
        }
        update(p);
    }
    void print(std::ostream &os, const node_pointer &p, bool &first) const {
        if(!p) return;
        print(os, p->left, first);
        os << (first ? "{" : " {") << p->index << ", " << p->value << "}";
        first = false;
        print(os, p->right, first);
    }

public:
    DynamicSegmentTree() : DynamicSegmentTree(std::numeric_limits<size_type>::max()) {};
    explicit DynamicSegmentTree(size_type n) : m_sz(n), m_root(nullptr) {}

    // 要素数を取得する．
    size_type size() const { return m_sz; }
    // k番目の要素をaに置き換える．O(log N).
    void set(size_type k, const value_type &a) { set(k, monoid_type(a)); }
    void set(size_type k, const monoid_type &a) {
        assert(k < size());
        set(m_root, k, a, 0, m_sz);
    }
    // k番目の要素を取得する．O(log N).
    value_type prod(size_type k) const {
        assert(k < size());
        return prod(m_root, k, 0, m_sz).value();
    }
    // 区間[l,r)の要素の総積を求める．O(log N).
    value_type prod(size_type l, size_type r) const {
        assert(l <= r and r <= size());
        return prod(m_root, l, r, 0, m_sz).value();
    }
    // 区間全体の要素の総積を取得する．O(1).
    value_type prod_all() const { return (m_root ? m_root->product : monoid_type::one()).value(); }
    // pred(prod(l,r))==true となる区間の最右位値rを二分探索する．
    // ただし，区間[l,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    size_type most_right(size_type l) const {
        return most_right(l, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    size_type most_right(size_type l, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(l <= size());
        assert(pred(monoid_type::one().value()));
        monoid_type &&product = monoid_type::one();
        return most_right(m_root, l, pred, 0, m_sz, product);
    }
    // pred(prod(l,r))==true となる区間の最左位値lを二分探索する．
    // ただし，区間[0,r)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
    template <bool (*pred)(value_type)>
    size_type most_left(int r) const {
        return most_left(r, [](const value_type &x) -> bool { return pred(x); });
    }
    template <typename Pred>
    size_type most_left(size_type r, Pred pred) const {
        static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
        assert(r <= size());
        assert(pred(monoid_type::one().value()));
        value_type &&product = monoid_type::one();
        return most_left(m_root, r, pred, 0, m_sz, product);
    }
    void reset(size_type k) { reset(m_root, k, k + 1, 0, m_sz); }
    void reset(size_type l, size_type r) {
        assert(l <= r and r <= size());
        reset(m_root, l, r, 0, m_sz);
    }
    void reset() { m_root.reset(); }

    friend std::ostream &operator<<(std::ostream &os, const DynamicSegmentTree &rhs) {
        os << "[";
        bool first = true;
        rhs.print(os, rhs.m_root, first);
        return os << "]";
    }
};

template <typename S>
using range_minimum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::minimum<S>>;

template <typename S>
using range_maximum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::maximum<S>>;

template <typename S>
using range_sum_dynamic_segment_tree = DynamicSegmentTree<algebra::monoid::addition<S>>;

}  // namespace dynamic_segment_tree

}  // namespace algorithm