単位元で無い要素が疎なセグメント木
(Src/DataStructure/SegmentTree/SparseSegmentTree.hpp)

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

概要

$N$ がめっちゃでかいセグ木をオンラインで要求されて座圧できないときにどうぞ。

コンストラクタの第二引数にメモリプールのサイズを指定できます(メモリプール(大嘘)で、vectorをreserveするだけです)

モノイドの雛形はこちらから。

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

        return ;
    }
};

TODO

• maxRightやminLeftを実装する
• ノードを作りすぎない工夫をする

参考

• Dynamic Segment Tree の ACL 風実装
• 動的な Segment Tree のテクニック

Depends on

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

Verified with

• Test/AtCoder/abc403_g.test.cpp
• Test/LC/point_set_range_composite_large_array.test.cpp
• Test/My/DataStructure/SegmentTree/SparseSegmentTreeGetTest.test.cpp

Code

#pragma once

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

#include <cassert>
#include <limits>
#include <optional>
#include <vector>

namespace zawa {

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

    using VM = Monoid;

    using V = typename VM::Element;

    using OM = Monoid;

    using O = typename OM::Element;

    SparseSegmentTree() = default;

    explicit SparseSegmentTree(usize n, usize poolSize = 0u) : m_n{n}, m_pool(1) {
        m_pool.reserve(poolSize);
    }

    inline usize size() const {
        return m_n;
    }

    void assign(usize p, V v) {
        assert(p < size());
        set(0, p, v, 0, size());
    }

    [[nodiscard]] V get(usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V operator[](usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return product(0, l, r, 0, size());
    }

private:

    struct node {
        static constexpr usize INVALID = std::numeric_limits<usize>::max();
        usize lch{INVALID}, rch{INVALID};
        V v{VM::identity()};
    };

    static constexpr usize mid(usize l, usize r) {
        return (l & r) + ((l ^ r) >> 1);
    }
    
    void set(usize i, usize p, const V& v, usize l, usize r) {
        if (l + 1 == r) {
            m_pool[i].v = v;
            return;
        }
        const usize m = mid(l, r);
        if (p < m) {
            if (m_pool[i].lch == node::INVALID) m_pool[i].lch = makeNode();
            set(m_pool[i].lch, p, v, l, m);
        }
        else {
            if (m_pool[i].rch == node::INVALID) m_pool[i].rch = makeNode();
            set(m_pool[i].rch, p, v, m, r);
        }
        m_pool[i].v = VM::operation(
                m_pool[i].lch == node::INVALID ? VM::identity() : m_pool[m_pool[i].lch].v,
                m_pool[i].rch == node::INVALID ? VM::identity() : m_pool[m_pool[i].rch].v
                );
    }

    V get(usize i, usize p, usize l, usize r) const {
        if (i == node::INVALID) return VM::identity();
        if (l + 1 == r) return m_pool[i].v;
        const usize m = mid(l, r);
        if (p < m) return get(m_pool[i].lch, p, l, m);
        else return get(m_pool[i].rch, p, m, r);
    }

    V product(usize i, usize l, usize r, usize curL, usize curR) const {
        if (i == node::INVALID) return VM::identity();
        if (r <= curL or curR <= l) return VM::identity();
        if (l <= curL and curR <= r) return m_pool[i].v;
        else {
            const usize m = mid(curL, curR);
            return VM::operation(
                        product(m_pool[i].lch, l, r, curL, m),
                        product(m_pool[i].rch, l, r, m, curR)
                    );
        }
    }

    usize makeNode() {
        usize res = m_pool.size();
        m_pool.emplace_back();
        return res;
    }

    usize m_n{};

    std::vector<node> m_pool{};
};

} // namespace zawa

#line 2 "Src/DataStructure/SegmentTree/SparseSegmentTree.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/SparseSegmentTree.hpp"

#include <cassert>
#include <limits>
#include <optional>
#include <vector>

namespace zawa {

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

    using VM = Monoid;

    using V = typename VM::Element;

    using OM = Monoid;

    using O = typename OM::Element;

    SparseSegmentTree() = default;

    explicit SparseSegmentTree(usize n, usize poolSize = 0u) : m_n{n}, m_pool(1) {
        m_pool.reserve(poolSize);
    }

    inline usize size() const {
        return m_n;
    }

    void assign(usize p, V v) {
        assert(p < size());
        set(0, p, v, 0, size());
    }

    [[nodiscard]] V get(usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V operator[](usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return product(0, l, r, 0, size());
    }

private:

    struct node {
        static constexpr usize INVALID = std::numeric_limits<usize>::max();
        usize lch{INVALID}, rch{INVALID};
        V v{VM::identity()};
    };

    static constexpr usize mid(usize l, usize r) {
        return (l & r) + ((l ^ r) >> 1);
    }
    
    void set(usize i, usize p, const V& v, usize l, usize r) {
        if (l + 1 == r) {
            m_pool[i].v = v;
            return;
        }
        const usize m = mid(l, r);
        if (p < m) {
            if (m_pool[i].lch == node::INVALID) m_pool[i].lch = makeNode();
            set(m_pool[i].lch, p, v, l, m);
        }
        else {
            if (m_pool[i].rch == node::INVALID) m_pool[i].rch = makeNode();
            set(m_pool[i].rch, p, v, m, r);
        }
        m_pool[i].v = VM::operation(
                m_pool[i].lch == node::INVALID ? VM::identity() : m_pool[m_pool[i].lch].v,
                m_pool[i].rch == node::INVALID ? VM::identity() : m_pool[m_pool[i].rch].v
                );
    }

    V get(usize i, usize p, usize l, usize r) const {
        if (i == node::INVALID) return VM::identity();
        if (l + 1 == r) return m_pool[i].v;
        const usize m = mid(l, r);
        if (p < m) return get(m_pool[i].lch, p, l, m);
        else return get(m_pool[i].rch, p, m, r);
    }

    V product(usize i, usize l, usize r, usize curL, usize curR) const {
        if (i == node::INVALID) return VM::identity();
        if (r <= curL or curR <= l) return VM::identity();
        if (l <= curL and curR <= r) return m_pool[i].v;
        else {
            const usize m = mid(curL, curR);
            return VM::operation(
                        product(m_pool[i].lch, l, r, curL, m),
                        product(m_pool[i].rch, l, r, m, curR)
                    );
        }
    }

    usize makeNode() {
        usize res = m_pool.size();
        m_pool.emplace_back();
        return res;
    }

    usize m_n{};

    std::vector<node> m_pool{};
};

} // namespace zawa

Back to top page