Dual Segment Tree (可換モノイド)
(Src/DataStructure/SegmentTree/CommutativeDualSegmentTree.hpp)

• View this file on GitHub
• Last update: 2025-06-24 16:23:43+09:00
• Include: #include "Src/DataStructure/SegmentTree/CommutativeDualSegmentTree.hpp"

ドキュメントを書く気力が行方不明！

テンプレート引数

struct M {
    using Element = ;
    static Element identity() {
    }
    static Element operation(Element L, Element R) {
    }
};

using O = Monoid::Element

operation(u32 l, u32 r, const O& v) 半開区間 $[l, r)$ に $v$ を合成(ACLでいうcomposition)

• $O(\log n)$

operation(u32 i, const O& v)

• $O(\log n)$
• 未verify

assign(u32 i, const O& v) $i$ 番目の要素に $v$ を「代入」

• $O(\log n)$

Operator operator[](u32 i)

• $i$ 番目の要素を取得
• $O(\log n)$

Depends on

• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Dual Segment Tree (非可換対応) (Src/DataStructure/SegmentTree/DualSegmentTree.hpp)

Verified with

• Test/AOJ/DSL_2_D.test.cpp
• Test/AOJ/DSL_2_E.test.cpp
• ABC332-F Random Update Query (a <- ap + qの処理) (Test/AtCoder/abc332_f.test.cpp)
• Test/LC/range_affine_point_get.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Monoid/MonoidConcept.hpp"

#include <bit>
#include <cassert>
#include <vector>
#include <iterator>
#include <ostream>

namespace zawa {

template <concepts::Monoid Monoid>
class CommutativeDualSegmentTree {
public:

    using OM = Monoid;

    using O = typename OM::Element;

    using VM = Monoid;

    using V = typename VM::Element;

    CommutativeDualSegmentTree() = default;

    explicit CommutativeDualSegmentTree(usize n) 
        : m_n{ n }, m_dat((n << 1), VM::identity()) {}

    explicit CommutativeDualSegmentTree(const std::vector<O>& dat) 
        : m_n{ dat.size() }, m_dat((m_n << 1), VM::identity()) {
        initDat(dat.begin(), dat.end());
    }

    template <class InputIterator>
    CommutativeDualSegmentTree(InputIterator first, InputIterator last)
        : m_n{ static_cast<usize>(std::distance(first, last)) }, m_dat((m_n << 1), OM::identity()) {
        initDat(first, last);
    }

    [[nodiscard]] inline usize size() const noexcept {
        return m_n;
    }

    virtual void operation(usize l, usize r, const O& v) {
        assert(l <= r and r <= size());
        for (l += size(), r += size() ; l < r ; l = parent(l), r = parent(r)) {
            if (l & 1) {
                m_dat[l] = OM::operation(m_dat[l], v);
                l++;
            }
            if (r & 1) {
                r--;
                m_dat[r] = OM::operation(m_dat[r], v);
            }
        }
    }

    // 未verify
    virtual void operation(usize i, const O& o) {
        assert(i < size());
        m_dat[i + size()] = OM::operation(m_dat[i + size()], o);
    }

    void assign(usize i, const V& v) {
        assert(i < size());
        push(i);
        m_dat[i + size()] = v;
    }

    [[nodiscard]] virtual V operator[](usize i) {
        assert(i < size());
        V res{ VM::identity() };
        for (i += size() ; i ; i = parent(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const CommutativeDualSegmentTree seg) {
        usize size{ seg.m_dat.size() };
        for (usize i{1} ; i < size ; i++) {
            os << seg.m_dat[i] << (i + 1 == size ? "" : " ");
        }
        return os;
    }

protected:

    static constexpr usize parent(usize v) noexcept {
        return v >> 1;
    }

    static constexpr usize left(usize v) noexcept {
        return v << 1;
    }

    static constexpr usize right(usize v) noexcept {
        return v << 1 | 1;
    }

    usize m_n;

    std::vector<V> m_dat;

    template <class InputIterator>
    inline void initDat(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            m_dat[size() + std::distance(first, it)] = *it;
        }
    }

    void push(usize i) {
        assert(i < size());
        i += size();
        usize height{ 64u - std::countl_zero(i) };
        for (usize h{ height } ; --h ; ) {
            usize v{ i >> h };
            m_dat[left(v)] = OM::operation(m_dat[left(v)], m_dat[v]);
            m_dat[right(v)] = OM::operation(m_dat[right(v)], m_dat[v]);
            m_dat[v] = OM::identity();
        }
    }

};

} // namespace zawa

#line 2 "Src/DataStructure/SegmentTree/CommutativeDualSegmentTree.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SegmentTree/CommutativeDualSegmentTree.hpp"

#include <bit>
#include <cassert>
#include <vector>
#include <iterator>
#include <ostream>

namespace zawa {

template <concepts::Monoid Monoid>
class CommutativeDualSegmentTree {
public:

    using OM = Monoid;

    using O = typename OM::Element;

    using VM = Monoid;

    using V = typename VM::Element;

    CommutativeDualSegmentTree() = default;

    explicit CommutativeDualSegmentTree(usize n) 
        : m_n{ n }, m_dat((n << 1), VM::identity()) {}

    explicit CommutativeDualSegmentTree(const std::vector<O>& dat) 
        : m_n{ dat.size() }, m_dat((m_n << 1), VM::identity()) {
        initDat(dat.begin(), dat.end());
    }

    template <class InputIterator>
    CommutativeDualSegmentTree(InputIterator first, InputIterator last)
        : m_n{ static_cast<usize>(std::distance(first, last)) }, m_dat((m_n << 1), OM::identity()) {
        initDat(first, last);
    }

    [[nodiscard]] inline usize size() const noexcept {
        return m_n;
    }

    virtual void operation(usize l, usize r, const O& v) {
        assert(l <= r and r <= size());
        for (l += size(), r += size() ; l < r ; l = parent(l), r = parent(r)) {
            if (l & 1) {
                m_dat[l] = OM::operation(m_dat[l], v);
                l++;
            }
            if (r & 1) {
                r--;
                m_dat[r] = OM::operation(m_dat[r], v);
            }
        }
    }

    // 未verify
    virtual void operation(usize i, const O& o) {
        assert(i < size());
        m_dat[i + size()] = OM::operation(m_dat[i + size()], o);
    }

    void assign(usize i, const V& v) {
        assert(i < size());
        push(i);
        m_dat[i + size()] = v;
    }

    [[nodiscard]] virtual V operator[](usize i) {
        assert(i < size());
        V res{ VM::identity() };
        for (i += size() ; i ; i = parent(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const CommutativeDualSegmentTree seg) {
        usize size{ seg.m_dat.size() };
        for (usize i{1} ; i < size ; i++) {
            os << seg.m_dat[i] << (i + 1 == size ? "" : " ");
        }
        return os;
    }

protected:

    static constexpr usize parent(usize v) noexcept {
        return v >> 1;
    }

    static constexpr usize left(usize v) noexcept {
        return v << 1;
    }

    static constexpr usize right(usize v) noexcept {
        return v << 1 | 1;
    }

    usize m_n;

    std::vector<V> m_dat;

    template <class InputIterator>
    inline void initDat(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            m_dat[size() + std::distance(first, it)] = *it;
        }
    }

    void push(usize i) {
        assert(i < size());
        i += size();
        usize height{ 64u - std::countl_zero(i) };
        for (usize h{ height } ; --h ; ) {
            usize v{ i >> h };
            m_dat[left(v)] = OM::operation(m_dat[left(v)], m_dat[v]);
            m_dat[right(v)] = OM::operation(m_dat[right(v)], m_dat[v]);
            m_dat[v] = OM::identity();
        }
    }

};

} // namespace zawa

Back to top page