Persistent Segment Tree
(segment-tree/persistent-segment-tree.hpp)

• View this file on GitHub
• Last update: 2026-06-28 15:41:08+09:00
• Include: #include "segment-tree/persistent-segment-tree.hpp"

永続セグメント木

https://info.atcoder.jp/entry/algorithm_lectures/persistent_segment_tree

完全永続的（fully persistent）なセグメント木

https://nyaannyaan.github.io/library/segment-tree/persistent-segment-tree.hpp.html

PersistentSegmentTree<M> として使う． M は value_type, op(x,y), e() を持つモノイドを表す型．

set, apply, get, prod それぞれ以下のように 3 パターンの方法で呼び出せる

• set(p, v) : 最新の木で位置 p の値を v に更新した新たな木の根へのポインタを返す
• set(time, p, v) : 時刻 time の木で位置 p の値を v に更新した新たな木の根へのポインタを返す
• set(ptr, p, v) : 根が ptr の木で位置 p の値を v に更新した新たな木の根へのポインタを返す

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp

Code

#pragma once
#include "algebraic-structure/monoid.hpp"

template <class M, int MAX_NODES = 20000000>
REQUIRES(Monoid<M>)
struct PersistentSegmentTree {
  using T = typename M::value_type;

  struct Node {
    Node *l, *r;
    T v;
  };

 private:
  int n;
  vector<Node> nodes;
  vector<Node*> roots;
  Node* make_node(const T& v) {
    nodes.push_back(Node{nullptr, nullptr, v});
    return &nodes.back();
  }
  Node* merge(Node* l, Node* r) {
    nodes.push_back(Node{l, r, M::op(l->v, r->v)});
    return &nodes.back();
  }
  Node* build(int l, int r, const vector<T>& v) {
    if (l + 1 == r) return make_node(v[l]);
    return merge(build(l, (l + r) / 2, v), build((l + r) / 2, r, v));
  }
  Node* set(Node* x, int l, int r, int p, const T& v) {
    if (l + 1 == r) return make_node(v);
    int m = (l + r) / 2;
    return p < m ? merge(set(x->l, l, m, p, v), x->r) : merge(x->l, set(x->r, m, r, p, v));
  }
  Node* apply(Node* x, int l, int r, int p, const T& v) {
    if (l + 1 == r) return make_node(M::op(x->v, v));
    int m = (l + r) / 2;
    return p < m ? merge(apply(x->l, l, m, p, v), x->r) : merge(x->l, apply(x->r, m, r, p, v));
  }
  T prod(Node* x, int xl, int xr, int l, int r) {
    if (x == nullptr) return M::e();
    if (r <= xl || xr <= l) return M::e();
    if (l <= xl && xr <= r) return x->v;
    int xm = (xl + xr) / 2;
    return M::op(prod(x->l, xl, xm, l, r), prod(x->r, xm, xr, l, r));
  }

 public:
  PersistentSegmentTree() : PersistentSegmentTree(1) {}
  PersistentSegmentTree(int sz) : PersistentSegmentTree(vector<T>(sz, M::e())) {}
  PersistentSegmentTree(const vector<T>& v) : n(v.size()) {
    assert(n > 0);
    roots.reserve(300000);
    nodes.reserve(MAX_NODES);
    roots.push_back(build(0, n, v));
  }

  int get_recent_time() { return (int)roots.size() - 1; }
  Node* get_root(int time = -1) {
    if (time == -1) return roots.back();
    return roots[time];
  }

  T get(Node* x, int p) {
    assert(0 <= p && p < n);
    int l = 0, r = n;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (p < m) {
        x = x->l;
        r = m;
      } else {
        x = x->r;
        l = m;
      }
    }
    return x->v;
  }
  T get(int time, int p) { return get(roots[time], p); }
  T get(int p) { return get(roots.back(), p); }

  Node* set(Node* x, int p, T v) {
    assert(0 <= p && p < n);
    roots.push_back(set(x, 0, n, p, v));
    return roots.back();
  }
  Node* set(int time, int p, T v) { return set(roots[time], p, v); }
  Node* set(int p, T v) { return set(roots.back(), p, v); }

  Node* apply(Node* x, int p, T v) {
    assert(0 <= p && p < n);
    roots.push_back(apply(x, 0, n, p, v));
    return roots.back();
  }
  Node* apply(int time, int p, T v) { return apply(roots[time], p, v); }
  Node* apply(int p, T v) { return apply(roots.back(), p, v); }

  T all_prod(Node* x) { return x->v; }
  T all_prod(int time) { return roots[time]->v; }
  T all_prod() { return roots.back()->v; }

  T prod(Node* x, int l, int r) {
    if (l >= r) return M::e();
    assert(0 <= l && l <= r && r <= n);
    return prod(x, 0, n, l, r);
  }
  T prod(int time, int l, int r) { return prod(roots[time], l, r); }
  T prod(int l, int r) { return prod(roots.back(), l, r); }
};

/**
 * @brief Persistent Segment Tree
 * @docs docs/segment-tree/persistent-segment-tree.md
 */

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "segment-tree/persistent-segment-tree.hpp"

template <class M, int MAX_NODES = 20000000>
REQUIRES(Monoid<M>)
struct PersistentSegmentTree {
  using T = typename M::value_type;

  struct Node {
    Node *l, *r;
    T v;
  };

 private:
  int n;
  vector<Node> nodes;
  vector<Node*> roots;
  Node* make_node(const T& v) {
    nodes.push_back(Node{nullptr, nullptr, v});
    return &nodes.back();
  }
  Node* merge(Node* l, Node* r) {
    nodes.push_back(Node{l, r, M::op(l->v, r->v)});
    return &nodes.back();
  }
  Node* build(int l, int r, const vector<T>& v) {
    if (l + 1 == r) return make_node(v[l]);
    return merge(build(l, (l + r) / 2, v), build((l + r) / 2, r, v));
  }
  Node* set(Node* x, int l, int r, int p, const T& v) {
    if (l + 1 == r) return make_node(v);
    int m = (l + r) / 2;
    return p < m ? merge(set(x->l, l, m, p, v), x->r) : merge(x->l, set(x->r, m, r, p, v));
  }
  Node* apply(Node* x, int l, int r, int p, const T& v) {
    if (l + 1 == r) return make_node(M::op(x->v, v));
    int m = (l + r) / 2;
    return p < m ? merge(apply(x->l, l, m, p, v), x->r) : merge(x->l, apply(x->r, m, r, p, v));
  }
  T prod(Node* x, int xl, int xr, int l, int r) {
    if (x == nullptr) return M::e();
    if (r <= xl || xr <= l) return M::e();
    if (l <= xl && xr <= r) return x->v;
    int xm = (xl + xr) / 2;
    return M::op(prod(x->l, xl, xm, l, r), prod(x->r, xm, xr, l, r));
  }

 public:
  PersistentSegmentTree() : PersistentSegmentTree(1) {}
  PersistentSegmentTree(int sz) : PersistentSegmentTree(vector<T>(sz, M::e())) {}
  PersistentSegmentTree(const vector<T>& v) : n(v.size()) {
    assert(n > 0);
    roots.reserve(300000);
    nodes.reserve(MAX_NODES);
    roots.push_back(build(0, n, v));
  }

  int get_recent_time() { return (int)roots.size() - 1; }
  Node* get_root(int time = -1) {
    if (time == -1) return roots.back();
    return roots[time];
  }

  T get(Node* x, int p) {
    assert(0 <= p && p < n);
    int l = 0, r = n;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (p < m) {
        x = x->l;
        r = m;
      } else {
        x = x->r;
        l = m;
      }
    }
    return x->v;
  }
  T get(int time, int p) { return get(roots[time], p); }
  T get(int p) { return get(roots.back(), p); }

  Node* set(Node* x, int p, T v) {
    assert(0 <= p && p < n);
    roots.push_back(set(x, 0, n, p, v));
    return roots.back();
  }
  Node* set(int time, int p, T v) { return set(roots[time], p, v); }
  Node* set(int p, T v) { return set(roots.back(), p, v); }

  Node* apply(Node* x, int p, T v) {
    assert(0 <= p && p < n);
    roots.push_back(apply(x, 0, n, p, v));
    return roots.back();
  }
  Node* apply(int time, int p, T v) { return apply(roots[time], p, v); }
  Node* apply(int p, T v) { return apply(roots.back(), p, v); }

  T all_prod(Node* x) { return x->v; }
  T all_prod(int time) { return roots[time]->v; }
  T all_prod() { return roots.back()->v; }

  T prod(Node* x, int l, int r) {
    if (l >= r) return M::e();
    assert(0 <= l && l <= r && r <= n);
    return prod(x, 0, n, l, r);
  }
  T prod(int time, int l, int r) { return prod(roots[time], l, r); }
  T prod(int l, int r) { return prod(roots.back(), l, r); }
};

/**
 * @brief Persistent Segment Tree
 * @docs docs/segment-tree/persistent-segment-tree.md
 */

Back to top page