library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: Persistent Segment Tree
(datastructure/persistent_segtree.hpp)

概要

使い方

制約

計算量

Depends on

Verified with

Code

#pragma once
#include <cassert>
#include <vector>

#include "algebra/concept.hpp"
template <monoid M> struct persistent_segtree {
public:
    using S = typename M::S;
    explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
    }
    explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        nodes.reserve(2 * _n);
        if (_n > 0) build(v, 0, _n);
    }
    int size() const {
        return _n;
    }
    S get(int root, int p) const {
        assert(0 <= p && p < _n);
        int cur = root, l = 0, r = _n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p < mid) {
                cur = nodes[cur].l, r = mid;
            } else {
                cur = nodes[cur].r, l = mid;
            }
        }
        return nodes[cur].val;
    }
    int set(int root, int p, const S& x) {
        assert(0 <= p && p < _n);
        int res = copy(root);
        int cur = res, l = 0, r = _n;
        path.clear();
        while (r - l > 1) {
            path.push_back(cur);
            int mid = (l + r) / 2;
            if (p < mid) {
                int nxt = copy(nodes[cur].l);
                nodes[cur].l = nxt;
                cur = nxt, r = mid;
            } else {
                int nxt = copy(nodes[cur].r);
                nodes[cur].r = nxt;
                cur = nxt, l = mid;
            }
        }
        nodes[cur].val = x;
        for (int i = int(path.size()) - 1; i >= 0; i--) {
            node& v = nodes[path[i]];
            v.val = M::op(nodes[v.l].val, nodes[v.r].val);
        }
        return res;
    }
    S prod(int root, int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prod(root, 0, _n, l, r);
    }
    S all_prod(int root) const {
        return _n == 0 ? M::e() : nodes[root].val;
    }

private:
    struct node {
        int l, r;
        S val;
    };
    int _n;
    std::vector<node> nodes;
    std::vector<int> path;
    int copy(int v) {
        nodes.push_back(nodes[v]);
        return int(nodes.size()) - 1;
    }
    int build(const std::vector<S>& v, int l, int r) {
        if (r - l == 1) {
            nodes.push_back({-1, -1, v[l]});
            return int(nodes.size()) - 1;
        }
        int mid = (l + r) / 2;
        int res = int(nodes.size());
        nodes.push_back({-1, -1, M::e()});
        int lc = build(v, l, mid);
        int rc = build(v, mid, r);
        nodes[res].l = lc, nodes[res].r = rc;
        nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
        return res;
    }
    S prod(int cur, int nl, int nr, int l, int r) const {
        if (r <= nl || nr <= l) return M::e();
        if (l <= nl && nr <= r) return nodes[cur].val;
        int mid = (nl + nr) / 2;
        return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
    }
};
#line 2 "datastructure/persistent_segtree.hpp"
#include <cassert>
#include <vector>

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
    { x.fail } -> std::convertible_to<bool>;
};
#line 6 "datastructure/persistent_segtree.hpp"
template <monoid M> struct persistent_segtree {
public:
    using S = typename M::S;
    explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
    }
    explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        nodes.reserve(2 * _n);
        if (_n > 0) build(v, 0, _n);
    }
    int size() const {
        return _n;
    }
    S get(int root, int p) const {
        assert(0 <= p && p < _n);
        int cur = root, l = 0, r = _n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p < mid) {
                cur = nodes[cur].l, r = mid;
            } else {
                cur = nodes[cur].r, l = mid;
            }
        }
        return nodes[cur].val;
    }
    int set(int root, int p, const S& x) {
        assert(0 <= p && p < _n);
        int res = copy(root);
        int cur = res, l = 0, r = _n;
        path.clear();
        while (r - l > 1) {
            path.push_back(cur);
            int mid = (l + r) / 2;
            if (p < mid) {
                int nxt = copy(nodes[cur].l);
                nodes[cur].l = nxt;
                cur = nxt, r = mid;
            } else {
                int nxt = copy(nodes[cur].r);
                nodes[cur].r = nxt;
                cur = nxt, l = mid;
            }
        }
        nodes[cur].val = x;
        for (int i = int(path.size()) - 1; i >= 0; i--) {
            node& v = nodes[path[i]];
            v.val = M::op(nodes[v.l].val, nodes[v.r].val);
        }
        return res;
    }
    S prod(int root, int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prod(root, 0, _n, l, r);
    }
    S all_prod(int root) const {
        return _n == 0 ? M::e() : nodes[root].val;
    }

private:
    struct node {
        int l, r;
        S val;
    };
    int _n;
    std::vector<node> nodes;
    std::vector<int> path;
    int copy(int v) {
        nodes.push_back(nodes[v]);
        return int(nodes.size()) - 1;
    }
    int build(const std::vector<S>& v, int l, int r) {
        if (r - l == 1) {
            nodes.push_back({-1, -1, v[l]});
            return int(nodes.size()) - 1;
        }
        int mid = (l + r) / 2;
        int res = int(nodes.size());
        nodes.push_back({-1, -1, M::e()});
        int lc = build(v, l, mid);
        int rc = build(v, mid, r);
        nodes[res].l = lc, nodes[res].r = rc;
        nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
        return res;
    }
    S prod(int cur, int nl, int nr, int l, int r) const {
        if (r <= nl || nr <= l) return M::e();
        if (l <= nl && nr <= r) return nodes[cur].val;
        int mid = (nl + nr) / 2;
        return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
    }
};
Back to top page