Tree Vertex Set Subtree Product
(tree/tree-vertex-set-subtree-prod.hpp)

• View this file on GitHub
• Last update: 2026-09-05 04:46:11+09:00
• Include: #include "tree/tree-vertex-set-subtree-prod.hpp"

根付き木の頂点の値を更新し，部分木上のモノイド積を求める．

TreeVertexSetSubtreeProd<M> として使う．M はモノイドであり，その演算を $\circ$ とする．部分木の積は Euler Tour の行きがけ順に取る．

• TreeVertexSetSubtreeProd(g, vertex_value, root)：木 g を root を根として，頂点列 vertex_value から構築する．
• set(x, v)：頂点 $x$ の値を $v$ に変更する．
• apply(x, v)：頂点 $x$ の値を $A_x\gets A_x\circ v$ に変更する．
• prod(x)：頂点 $x$ の部分木に含まれる頂点の積を返す．

構築は $O(N)$ 時間，$O(N)$ 空間．各操作は $O(\log N)$ 時間．

資料

• Library Checker: Vertex Add Subtree Sum

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Segment Tree (segment-tree/segment-tree.hpp)
• Euler Tour of Tree (tree/euler-tour.hpp)

Verified with

• verify/tree/LC_vertex_add_subtree_sum.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"
#include "tree/euler-tour.hpp"
#include "segment-tree/segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetSubtreeProd {
  using T = M::value_type;
  TreeVertexSetSubtreeProd() {}
  template <class G>
  TreeVertexSetSubtreeProd(const G& g, const vector<T>& vertex_value, int root = 0) : n(g.size()) {
    assert((int)vertex_value.size() == n);
    tie(in_time, out_time) = EulerTour(g, root);
    vector<T> data(n);
    for (int x = 0; x < n; x++) data[in_time[x]] = vertex_value[x];
    seg = SegmentTree<M>(data);
  }
  void set(int x, T v) { seg.set(in_time[x], v); }
  void apply(int x, T v) { seg.apply(in_time[x], v); }
  T prod(int x) { return seg.prod(in_time[x], out_time[x]); }

 private:
  int n;
  vector<int> in_time, out_time;
  SegmentTree<M> seg;
};

/**
 * @brief Tree Vertex Set Subtree Product
 * @docs docs/tree/tree-vertex-set-subtree-prod.md
 */

#line 2 "tree/tree-vertex-set-subtree-prod.hpp"

#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 2 "tree/euler-tour.hpp"

template <class G>
pair<vector<int>, vector<int>> EulerTour(const G& g, int root = 0) {
  int n = g.size();
  assert(n > 0);
  assert(0 <= root && root < n);
  vector<int> in_time(n), out_time(n);
  vector<int> parent(n, -2), iter(n);
  parent[root] = -1;
  int t = 0;
  vector<int> st = {root};
  while (!st.empty()) {
    int x = st.back();
    if (iter[x] == 0) in_time[x] = t++;
    if (iter[x] == (int)g[x].size()) {
      out_time[x] = t;
      st.pop_back();
      continue;
    }
    int y = g[x][iter[x]++].to;
    if (y == parent[x]) continue;
    assert(parent[y] == -2);
    parent[y] = x;
    st.push_back(y);
  }
  assert(t == n);
  return {in_time, out_time};
}

/**
 * @brief Euler Tour of Tree
 * @docs docs/tree/euler-tour.md
 */
#line 3 "segment-tree/segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct SegmentTree {
  using T = typename M::value_type;

 private:
  int _n, size, log;
  vector<T> d;
  void update(int p) { d[p] = M::op(d[2 * p], d[2 * p + 1]); }

 public:
  SegmentTree() : SegmentTree(0) {}
  explicit SegmentTree(int sz) : SegmentTree(vector<T>(sz, M::e())) {}
  explicit SegmentTree(const vector<T>& v) : _n(v.size()) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d.assign(2 * size, M::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  void clear() { fill(d.begin(), d.end(), M::e()); }

  void set_without_update(int p, T v) { d[p + size] = v; }
  void all_update() {
    for (int i = size - 1; i > 0; i--) update(i);
  }
  T get(int p) {
    assert(0 <= p && p <= _n);
    return d[p + size];
  }
  void set(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = v;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = M::op(d[p], v);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T all_prod() { return d[1]; }
  T prod(int l, int r) {
    if (l >= r) return M::e();
    assert(0 <= l && l <= r && r <= _n);
    T sl = M::e(), sr = M::e();
    l += size, r += size;
    while (l < r) {
      if ((l & 1) != 0) sl = M::op(sl, d[l++]);
      if ((r & 1) != 0) sr = M::op(d[--r], sr);
      l >>= 1, r >>= 1;
    }
    return M::op(sl, sr);
  }

  template <bool (*f)(T)>
  int max_right(int l) const {
    return max_right(l, [](T x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) const {
    assert(0 <= l && l <= size);
    assert(f(M::e()));
    if (l == _n) return _n;
    l += size;
    T s = M::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(M::op(s, d[l]))) {
        while (l < size) {
          l <<= 1;
          if (f(M::op(s, d[l]))) s = M::op(s, d[l++]);
        }
        return l - size;
      }
      s = M::op(s, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(T)>
  int min_left(int r) const {
    return min_left(r, [](T x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) const {
    assert(0 <= r && r <= _n);
    assert(f(M::e()));
    if (r == 0) return 0;
    r += size;
    T s = M::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(M::op(d[r], s))) {
        while (r < size) {
          r <<= 1, r++;
          if (f(M::op(d[r], s))) s = M::op(d[r--], s);
        }
        return r + 1 - size;
      }
      s = M::op(d[r], s);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Segment Tree
 * @docs docs/segment-tree/segment-tree.md
 */
#line 6 "tree/tree-vertex-set-subtree-prod.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetSubtreeProd {
  using T = M::value_type;
  TreeVertexSetSubtreeProd() {}
  template <class G>
  TreeVertexSetSubtreeProd(const G& g, const vector<T>& vertex_value, int root = 0) : n(g.size()) {
    assert((int)vertex_value.size() == n);
    tie(in_time, out_time) = EulerTour(g, root);
    vector<T> data(n);
    for (int x = 0; x < n; x++) data[in_time[x]] = vertex_value[x];
    seg = SegmentTree<M>(data);
  }
  void set(int x, T v) { seg.set(in_time[x], v); }
  void apply(int x, T v) { seg.apply(in_time[x], v); }
  T prod(int x) { return seg.prod(in_time[x], out_time[x]); }

 private:
  int n;
  vector<int> in_time, out_time;
  SegmentTree<M> seg;
};

/**
 * @brief Tree Vertex Set Subtree Product
 * @docs docs/tree/tree-vertex-set-subtree-prod.md
 */

Back to top page