Range Set Range Prod
(segment-tree/range-set-range-prod.hpp)

View this file on GitHub
Last update: 2026-07-28 20:47:27+09:00
Include: #include "segment-tree/range-set-range-prod.hpp"

モノイド $(T,\cdot,e)$ の列に対する区間代入と区間積を扱う．

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

長さ $N$ の列 $A=(A_0,A_1,\dots,A_{N-1})$ に対し，空間計算量 $O(N)$ のもとで以下の操作を行える．

set(p, x)：$A_p\gets x$ とする．$O(\log N)$ 時間．
get(p)：$A_p$ を取得する．$O(\log N)$ 時間．
apply(p, x)：$A_p\gets x$ とする．$O(\log N)$ 時間．
apply(l, r, x)：$l\leq i\lt r$ に対して $A_i\gets x$ とする．償却 $O(\log N)$ 時間．
prod(l, r)：$A_l\cdot A_{l+1}\cdot\cdots\cdot A_{r-1}$ を取得する．$O(\log N)$ 時間．
all_prod()：$A_0\cdot A_1\cdot\cdots\cdot A_{N-1}$ を取得する．$O(1)$ 時間．
max_right(l, cond)：$\mathrm{cond}(A_l\cdot A_{l+1}\cdot\cdots\cdot A_{r-1})$ が真となる最大の $r$ を返す．$O(\log N)$ 時間．
min_left(r, cond)：$\mathrm{cond}(A_l\cdot A_{l+1}\cdot\cdots\cdot A_{r-1})$ が真となる最小の $l$ を返す．$O(\log N)$ 時間．

二分探索では cond(e) が真であり，判定が単調であることを要求する．

アルゴリズム

$x$ を代入するクエリごとに

\[x,\ x^2,\ x^4,\ \dots,\ x^{2^{\lceil\log N\rceil}}\]

を計算する．セグメント木の各節点が表す区間の長さは二冪なので，区間全体を $x$ に置き換えたときの積を $O(1)$ 回の参照で得られる．

$O(N/\log N)$ 回の区間代入ごとに全ての遅延値を子へ伝播し，保存した冪を破棄する．この伝播は $O(N)$ 時間なので，区間代入は償却 $O(\log N)$ 時間となる．全伝播が発生する単一の区間代入は最悪 $O(N)$ 時間かかる．

資料

区間代入/区間積 Θ(logN)/query

Depends on

Verified with

verify/segment-tree/LC_range_set_range_composite.test.cpp

Code

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

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

 private:
  int _n, size, log, history_limit;
  vector<T> d;
  vector<int> lz, height;
  vector<vector<T>> history;

  void update(int k) { d[k] = M::op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, int id) {
    d[k] = history[id][height[k]];
    if (k < size) lz[k] = id;
  }
  void push(int k) {
    if (lz[k] == -1) return;
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = -1;
  }
  void flush() {
    for (int k = 1; k < size; k++) push(k);
    history.clear();
  }
  int add_history(T x) {
    if ((int)history.size() == history_limit) flush();
    vector<T> power;
    power.reserve(log + 1);
    power.push_back(x);
    for (int i = 0; i < log; i++) power.push_back(M::op(power.back(), power.back()));
    history.push_back(move(power));
    return (int)history.size() - 1;
  }

 public:
  RangeSetRangeProd() : RangeSetRangeProd(0) {}
  explicit RangeSetRangeProd(int n) : RangeSetRangeProd(vector<T>(n, M::e())) {}
  explicit RangeSetRangeProd(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, M::e());
    lz = vector<int>(size, -1);
    height = vector<int>(2 * size);
    for (int k = size - 1; k > 0; k--) height[k] = height[2 * k] + 1;
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int k = size - 1; k > 0; k--) update(k);
    history_limit = max(1, size / (log + 1));
  }

  void set(int p, T x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  T prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return M::e();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    T sml = M::e(), smr = M::e();
    while (l < r) {
      if (l & 1) sml = M::op(sml, d[l++]);
      if (r & 1) smr = M::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return M::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, T x) { set(p, x); }
  void apply(int l, int r, T x) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;
    int id = add_history(x);
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, id);
        if (r & 1) all_apply(--r, id);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <bool (*g)(T)>
  int max_right(int l) {
    return max_right(l, [](T x) { return g(x); });
  }
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(M::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = M::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(M::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = 2 * l;
          if (g(M::op(sm, d[l]))) sm = M::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = M::op(sm, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(T)>
  int min_left(int r) {
    return min_left(r, [](T x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(M::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = M::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(M::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = 2 * r + 1;
          if (g(M::op(d[r], sm))) sm = M::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = M::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Range Set Range Prod
 * @docs docs/segment-tree/range-set-range-prod.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/range-set-range-prod.hpp"

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

 private:
  int _n, size, log, history_limit;
  vector<T> d;
  vector<int> lz, height;
  vector<vector<T>> history;

  void update(int k) { d[k] = M::op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, int id) {
    d[k] = history[id][height[k]];
    if (k < size) lz[k] = id;
  }
  void push(int k) {
    if (lz[k] == -1) return;
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = -1;
  }
  void flush() {
    for (int k = 1; k < size; k++) push(k);
    history.clear();
  }
  int add_history(T x) {
    if ((int)history.size() == history_limit) flush();
    vector<T> power;
    power.reserve(log + 1);
    power.push_back(x);
    for (int i = 0; i < log; i++) power.push_back(M::op(power.back(), power.back()));
    history.push_back(move(power));
    return (int)history.size() - 1;
  }

 public:
  RangeSetRangeProd() : RangeSetRangeProd(0) {}
  explicit RangeSetRangeProd(int n) : RangeSetRangeProd(vector<T>(n, M::e())) {}
  explicit RangeSetRangeProd(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, M::e());
    lz = vector<int>(size, -1);
    height = vector<int>(2 * size);
    for (int k = size - 1; k > 0; k--) height[k] = height[2 * k] + 1;
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int k = size - 1; k > 0; k--) update(k);
    history_limit = max(1, size / (log + 1));
  }

  void set(int p, T x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  T prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return M::e();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    T sml = M::e(), smr = M::e();
    while (l < r) {
      if (l & 1) sml = M::op(sml, d[l++]);
      if (r & 1) smr = M::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return M::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, T x) { set(p, x); }
  void apply(int l, int r, T x) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;
    int id = add_history(x);
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, id);
        if (r & 1) all_apply(--r, id);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <bool (*g)(T)>
  int max_right(int l) {
    return max_right(l, [](T x) { return g(x); });
  }
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(M::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = M::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(M::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = 2 * l;
          if (g(M::op(sm, d[l]))) sm = M::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = M::op(sm, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(T)>
  int min_left(int r) {
    return min_left(r, [](T x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(M::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = M::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(M::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = 2 * r + 1;
          if (g(M::op(d[r], sm))) sm = M::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = M::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Range Set Range Prod
 * @docs docs/segment-tree/range-set-range-prod.md
 */

Range Set Range Prod (segment-tree/range-set-range-prod.hpp)

アルゴリズム

資料

Depends on

Verified with

Code

Range Set Range Prod
(segment-tree/range-set-range-prod.hpp)