Range Chmin Chmax Add Range Sum
(segment-tree/range-chmin-chmax-add-range-sum.hpp)

• View this file on GitHub
• Last update: 2026-08-26 13:48:57+09:00
• Include: #include "segment-tree/range-chmin-chmax-add-range-sum.hpp"

列に対する区間 chmin，区間 chmax，区間加算，区間和取得を扱う．

RangeChminChmaxAddRangeSum<T> として使う．区間は半開区間 $[l,r)$ で指定する．

• RangeChminChmaxAddRangeSum<T>(n)：長さ $n$，全要素 $0$ で初期化する．
• RangeChminChmaxAddRangeSum<T>(a)：列 a で初期化する．
• set(p, x)：$A_p\gets x$ とする．
• get(p)：$A_p$ を返す．
• chmin(l, r, x)：$l\leq i\lt r$ に対して $A_i\gets\min(A_i,x)$ とする．
• chmax(l, r, x)：$l\leq i\lt r$ に対して $A_i\gets\max(A_i,x)$ とする．
• add(l, r, x)：$l\leq i\lt r$ に対して $A_i\gets A_i+x$ とする．
• sum(l, r) / prod(l, r)：$A_l+A_{l+1}+\cdots+A_{r-1}$ を返す．
• all_sum() / all_prod()：列全体の和を返す．

空区間への更新は何もせず，空区間の和は $0$ とする．T は符号付き整数型とする．B = numeric_limits<T>::max() / 4 として，全ての要素と chmin, chmax の引数が $(-B,B)$ に収まり，番兵を含む中間演算と総和が T の範囲に収まることを要求する．

計算量

• set, get, add, sum：$O(\log N)$
• chmin, chmax：償却 $O(\log^2 N)$
• all_sum：$O(1)$

空間計算量は $O(N)$．

仕組み

各節点に区間の最小値・二番目の最小値・最大値・二番目の最大値，最小値と最大値の個数，区間の要素数と総和を持つ．

chmin の上限が二番目の最大値より大きければ，最大値を取る要素だけが変化するため，節点の情報を直接更新できる．chmax も同様である．直接更新できない場合は SegmentTreeBeats の fail を立て，作用を子へ伝播して節点を再構築する．

資料

• Library Checker: Range Chmin Chmax Add Range Sum
• atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)
• Segment Tree Beats (segment-tree/segment-tree-beats.hpp)

Verified with

• verify/segment-tree/LC_range_chmin_chmax_add_range_sum.test.cpp

Code

#pragma once

#include "segment-tree/segment-tree-beats.hpp"

namespace RangeChminChmaxAddRangeSumImpl {
template <class T>
struct S {
  static_assert(numeric_limits<T>::is_integer && numeric_limits<T>::is_signed);
  static constexpr T INF = numeric_limits<T>::max() / 4;
  T lo, hi, lo2, hi2, sum;
  int sz, nlo, nhi;
  bool fail;
  S() : lo(INF), hi(-INF), lo2(INF), hi2(-INF), sum(0), sz(0), nlo(0), nhi(0), fail(false) {}
  S(T x, int sz_) : lo(x), hi(x), lo2(INF), hi2(-INF), sum(x * sz_), sz(sz_), nlo(sz_), nhi(sz_), fail(false) {}
};
template <class T>
T second_lowest(T a, T a2, T b, T b2) {
  return a == b ? min(a2, b2) : a2 <= b ? a2 : b2 <= a ? b2 : max(a, b);
}
template <class T>
T second_highest(T a, T a2, T b, T b2) {
  return a == b ? max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : min(a, b);
}
template <class T>
struct ValueMonoid {
  using value_type = S<T>;
  static S<T> op(S<T> l, S<T> r) {
    S<T> x;
    x.lo = min(l.lo, r.lo), x.hi = max(l.hi, r.hi);
    x.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
    x.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
    x.sum = l.sum + r.sum, x.sz = l.sz + r.sz;
    x.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
    x.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
    return x;
  }
  static S<T> e() { return S<T>(); }
};
template <class T>
struct F {
  T lb, ub, bias;
  F(T lb_ = -S<T>::INF, T ub_ = S<T>::INF, T bias_ = 0) : lb(lb_), ub(ub_), bias(bias_) {}
  static F chmin(T x) { return F(-S<T>::INF, x, 0); }
  static F chmax(T x) { return F(x, S<T>::INF, 0); }
  static F add(T x) { return F(-S<T>::INF, S<T>::INF, x); }
};
template <class T>
struct OperatorMonoid {
  using value_type = F<T>;
  static F<T> op(F<T> f, F<T> g) {
    F<T> h;
    h.lb = max(min(g.lb + g.bias, f.ub), f.lb) - g.bias;
    h.ub = min(max(g.ub + g.bias, f.lb), f.ub) - g.bias;
    h.bias = g.bias + f.bias;
    return h;
  }
  static F<T> e() { return F<T>(); }
};
template <class T>
struct Action {
  using value_monoid = ValueMonoid<T>;
  using operator_monoid = OperatorMonoid<T>;
  static S<T> mapping(F<T> f, S<T> x) {
    if (x.sz == 0) return S<T>();
    if (x.lo == x.hi || f.lb == f.ub || f.lb >= x.hi || f.ub <= x.lo) {
      return S<T>(min(max(x.lo, f.lb), f.ub) + f.bias, x.sz);
    }
    if (x.lo2 == x.hi) {
      x.lo = x.hi2 = max(x.lo, f.lb) + f.bias;
      x.hi = x.lo2 = min(x.hi, f.ub) + f.bias;
      x.sum = x.lo * x.nlo + x.hi * x.nhi;
      return x;
    }
    if (f.lb < x.lo2 && f.ub > x.hi2) {
      T next_lo = max(x.lo, f.lb), next_hi = min(x.hi, f.ub);
      x.sum += (next_lo - x.lo) * x.nlo - (x.hi - next_hi) * x.nhi + f.bias * x.sz;
      x.lo = next_lo + f.bias, x.hi = next_hi + f.bias;
      x.lo2 += f.bias, x.hi2 += f.bias;
      return x;
    }
    x.fail = true;
    return x;
  }
};
template <class T>
vector<S<T>> init(const vector<T>& a) {
  vector<S<T>> v;
  v.reserve(a.size());
  for (T x : a) v.emplace_back(x, 1);
  return v;
}
}  // namespace RangeChminChmaxAddRangeSumImpl

template <class T>
struct RangeChminChmaxAddRangeSum : SegmentTreeBeats<RangeChminChmaxAddRangeSumImpl::Action<T>> {
  using Impl = RangeChminChmaxAddRangeSumImpl::Action<T>;
  using S = RangeChminChmaxAddRangeSumImpl::S<T>;
  using F = RangeChminChmaxAddRangeSumImpl::F<T>;
  using base = SegmentTreeBeats<Impl>;
  RangeChminChmaxAddRangeSum() : base() {}
  explicit RangeChminChmaxAddRangeSum(int n) : base(vector<S>(n, S(T(0), 1))) {}
  explicit RangeChminChmaxAddRangeSum(const vector<T>& a) : base(RangeChminChmaxAddRangeSumImpl::init(a)) {}
  void set(int p, T x) { base::set(p, S(x, 1)); }
  T get(int p) { return base::get(p).sum; }
  void chmin(int l, int r, T x) { base::apply(l, r, F::chmin(x)); }
  void chmax(int l, int r, T x) { base::apply(l, r, F::chmax(x)); }
  void add(int l, int r, T x) { base::apply(l, r, F::add(x)); }
  T sum(int l, int r) { return base::prod(l, r).sum; }
  T prod(int l, int r) { return sum(l, r); }
  T all_sum() { return base::all_prod().sum; }
  T all_prod() { return all_sum(); }
};

/**
 * @brief Range Chmin Chmax Add Range Sum
 * @docs docs/segment-tree/range-chmin-chmax-add-range-sum.md
 */

#line 2 "segment-tree/range-chmin-chmax-add-range-sum.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 3 "algebraic-structure/monoid-action.hpp"

#ifdef __cpp_concepts
template <class A>
concept MonoidAction = Monoid<typename A::value_monoid> && Monoid<typename A::operator_monoid> && requires(typename A::value_monoid::value_type x, typename A::operator_monoid::value_type f) {
  typename A::value_monoid;
  typename A::operator_monoid;
  { A::mapping(f, x) } -> same_as<typename A::value_monoid::value_type>;
};
#endif
#line 3 "segment-tree/lazy-segment-tree.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct LazySegmentTree {
  using VM = typename A::value_monoid;
  using OM = typename A::operator_monoid;
  using T = typename VM::value_type;
  using F = typename OM::value_type;

 protected:
  int _n, size, log;
  vector<T> d;
  vector<F> lz;

  void update(int k) { d[k] = VM::op(d[2 * k], d[2 * k + 1]); }
  virtual void all_apply(int k, F f) {
    d[k] = A::mapping(f, d[k]);
    if (k < size) lz[k] = OM::op(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = OM::e();
  }

 public:
  LazySegmentTree() : LazySegmentTree(0) {}
  explicit LazySegmentTree(int n) : LazySegmentTree(vector<T>(n, VM::e())) {}
  explicit LazySegmentTree(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, VM::e());
    lz = vector<F>(size, OM::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  virtual ~LazySegmentTree() = default;

  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 VM::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 = VM::e(), smr = VM::e();
    while (l < r) {
      if (l & 1) sml = VM::op(sml, d[l++]);
      if (r & 1) smr = VM::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return VM::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = A::mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;
    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++, f);
        if (r & 1) all_apply(--r, f);
        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(VM::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = VM::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(VM::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(VM::op(sm, d[l]))) sm = VM::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = VM::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(VM::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = VM::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(VM::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(VM::op(d[r], sm))) sm = VM::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = VM::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Lazy Segment Tree
 * @docs docs/segment-tree/lazy-segment-tree.md
 */
#line 3 "segment-tree/segment-tree-beats.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct SegmentTreeBeats : LazySegmentTree<A> {
  using base = LazySegmentTree<A>;
  using T = typename base::T;
  using F = typename base::F;

  SegmentTreeBeats() : base() {}
  explicit SegmentTreeBeats(int n) : base(n) {}
  explicit SegmentTreeBeats(const vector<T>& v) : base(v) {}

 protected:
  void all_apply(int k, F f) override {
    this->d[k] = A::mapping(f, this->d[k]);
    if (k < this->size) {
      this->lz[k] = base::OM::op(f, this->lz[k]);
      if (this->d[k].fail) this->push(k), this->update(k);
    }
  }
};

/**
 * @brief Segment Tree Beats
 * @docs docs/segment-tree/segment-tree-beats.md
 */
#line 4 "segment-tree/range-chmin-chmax-add-range-sum.hpp"

namespace RangeChminChmaxAddRangeSumImpl {
template <class T>
struct S {
  static_assert(numeric_limits<T>::is_integer && numeric_limits<T>::is_signed);
  static constexpr T INF = numeric_limits<T>::max() / 4;
  T lo, hi, lo2, hi2, sum;
  int sz, nlo, nhi;
  bool fail;
  S() : lo(INF), hi(-INF), lo2(INF), hi2(-INF), sum(0), sz(0), nlo(0), nhi(0), fail(false) {}
  S(T x, int sz_) : lo(x), hi(x), lo2(INF), hi2(-INF), sum(x * sz_), sz(sz_), nlo(sz_), nhi(sz_), fail(false) {}
};
template <class T>
T second_lowest(T a, T a2, T b, T b2) {
  return a == b ? min(a2, b2) : a2 <= b ? a2 : b2 <= a ? b2 : max(a, b);
}
template <class T>
T second_highest(T a, T a2, T b, T b2) {
  return a == b ? max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : min(a, b);
}
template <class T>
struct ValueMonoid {
  using value_type = S<T>;
  static S<T> op(S<T> l, S<T> r) {
    S<T> x;
    x.lo = min(l.lo, r.lo), x.hi = max(l.hi, r.hi);
    x.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
    x.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
    x.sum = l.sum + r.sum, x.sz = l.sz + r.sz;
    x.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
    x.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
    return x;
  }
  static S<T> e() { return S<T>(); }
};
template <class T>
struct F {
  T lb, ub, bias;
  F(T lb_ = -S<T>::INF, T ub_ = S<T>::INF, T bias_ = 0) : lb(lb_), ub(ub_), bias(bias_) {}
  static F chmin(T x) { return F(-S<T>::INF, x, 0); }
  static F chmax(T x) { return F(x, S<T>::INF, 0); }
  static F add(T x) { return F(-S<T>::INF, S<T>::INF, x); }
};
template <class T>
struct OperatorMonoid {
  using value_type = F<T>;
  static F<T> op(F<T> f, F<T> g) {
    F<T> h;
    h.lb = max(min(g.lb + g.bias, f.ub), f.lb) - g.bias;
    h.ub = min(max(g.ub + g.bias, f.lb), f.ub) - g.bias;
    h.bias = g.bias + f.bias;
    return h;
  }
  static F<T> e() { return F<T>(); }
};
template <class T>
struct Action {
  using value_monoid = ValueMonoid<T>;
  using operator_monoid = OperatorMonoid<T>;
  static S<T> mapping(F<T> f, S<T> x) {
    if (x.sz == 0) return S<T>();
    if (x.lo == x.hi || f.lb == f.ub || f.lb >= x.hi || f.ub <= x.lo) {
      return S<T>(min(max(x.lo, f.lb), f.ub) + f.bias, x.sz);
    }
    if (x.lo2 == x.hi) {
      x.lo = x.hi2 = max(x.lo, f.lb) + f.bias;
      x.hi = x.lo2 = min(x.hi, f.ub) + f.bias;
      x.sum = x.lo * x.nlo + x.hi * x.nhi;
      return x;
    }
    if (f.lb < x.lo2 && f.ub > x.hi2) {
      T next_lo = max(x.lo, f.lb), next_hi = min(x.hi, f.ub);
      x.sum += (next_lo - x.lo) * x.nlo - (x.hi - next_hi) * x.nhi + f.bias * x.sz;
      x.lo = next_lo + f.bias, x.hi = next_hi + f.bias;
      x.lo2 += f.bias, x.hi2 += f.bias;
      return x;
    }
    x.fail = true;
    return x;
  }
};
template <class T>
vector<S<T>> init(const vector<T>& a) {
  vector<S<T>> v;
  v.reserve(a.size());
  for (T x : a) v.emplace_back(x, 1);
  return v;
}
}  // namespace RangeChminChmaxAddRangeSumImpl

template <class T>
struct RangeChminChmaxAddRangeSum : SegmentTreeBeats<RangeChminChmaxAddRangeSumImpl::Action<T>> {
  using Impl = RangeChminChmaxAddRangeSumImpl::Action<T>;
  using S = RangeChminChmaxAddRangeSumImpl::S<T>;
  using F = RangeChminChmaxAddRangeSumImpl::F<T>;
  using base = SegmentTreeBeats<Impl>;
  RangeChminChmaxAddRangeSum() : base() {}
  explicit RangeChminChmaxAddRangeSum(int n) : base(vector<S>(n, S(T(0), 1))) {}
  explicit RangeChminChmaxAddRangeSum(const vector<T>& a) : base(RangeChminChmaxAddRangeSumImpl::init(a)) {}
  void set(int p, T x) { base::set(p, S(x, 1)); }
  T get(int p) { return base::get(p).sum; }
  void chmin(int l, int r, T x) { base::apply(l, r, F::chmin(x)); }
  void chmax(int l, int r, T x) { base::apply(l, r, F::chmax(x)); }
  void add(int l, int r, T x) { base::apply(l, r, F::add(x)); }
  T sum(int l, int r) { return base::prod(l, r).sum; }
  T prod(int l, int r) { return sum(l, r); }
  T all_sum() { return base::all_prod().sum; }
  T all_prod() { return all_sum(); }
};

/**
 * @brief Range Chmin Chmax Add Range Sum
 * @docs docs/segment-tree/range-chmin-chmax-add-range-sum.md
 */

Back to top page