双対セグメント木 (作用が可換な場合)
(library/datastructure/segment_tree/commutative_dual_segment_tree.hpp)

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Include: #include "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp"

双対セグメント木 (作用が可換な場合)

作用の可換性を仮定した場合、作用を伝播させる必要がないため、伝播処理をサボることで定数倍改善を測ることができる。

Required by

• 双対セグメント木 (library/datastructure/segment_tree/dual_segment_tree.hpp)

Verified with

• test/src/datastructure/segment_tree/commutative_dual_segment_tree/DSL_2_E.test.cpp
• test/src/datastructure/segment_tree/commutative_dual_segment_tree/rectilinear_polygons.test.cpp
• test/src/datastructure/segment_tree/dual_segment_tree/DSL_2_D.test.cpp
• test/src/datastructure/segment_tree/dual_segment_tree/DSL_2_E.test.cpp
• test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp
• test/src/datastructure/segment_tree/dual_segment_tree/rectilinear_polygons.test.cpp

Code

#ifndef SUISEN_COM_DUAL_SEGTREE
#define SUISEN_COM_DUAL_SEGTREE

#include <cassert>
#include <vector>

namespace suisen {
    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct CommutativeDualSegmentTree {
        CommutativeDualSegmentTree() = default;
        CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {}
        CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {}
        CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {}

        T operator[](int i) const {
            assert(0 <= i and i < n);
            T res = data[i];
            for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res);
            return res;
        }
        T get(int i) const {
            return (*this)[i];
        }
        void apply(int l, int r, const F& f) {
            assert(0 <= l and r <= n);
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) apply(l++, f);
                if (r & 1) apply(--r, f);
            }
        }
    protected:
        int n, m;
        std::vector<T> data;
        std::vector<F> lazy;

        void apply(int k, const F& f) {
            if (k < m) {
                lazy[k] = composition(f, lazy[k]);
            } else if (k - m < n) {
                data[k - m] = mapping(f, data[k - m]);
            }
        }
    private:
        static int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }
    };
} // namespace suisen

#endif // SUISEN_COM_DUAL_SEGTREE

#line 1 "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp"



#include <cassert>
#include <vector>

namespace suisen {
    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct CommutativeDualSegmentTree {
        CommutativeDualSegmentTree() = default;
        CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {}
        CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {}
        CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {}

        T operator[](int i) const {
            assert(0 <= i and i < n);
            T res = data[i];
            for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res);
            return res;
        }
        T get(int i) const {
            return (*this)[i];
        }
        void apply(int l, int r, const F& f) {
            assert(0 <= l and r <= n);
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) apply(l++, f);
                if (r & 1) apply(--r, f);
            }
        }
    protected:
        int n, m;
        std::vector<T> data;
        std::vector<F> lazy;

        void apply(int k, const F& f) {
            if (k < m) {
                lazy[k] = composition(f, lazy[k]);
            } else if (k - m < n) {
                data[k - m] = mapping(f, data[k - m]);
            }
        }
    private:
        static int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }
    };
} // namespace suisen

Back to top page