Range Add Range Min
(data-structure/range-add-range-min.hpp)

• View this file on GitHub
• Last update: 2026-07-08 03:16:39+09:00
• Include: #include "data-structure/range-add-range-min.hpp"

列 $A=(A_0,A_1,\dots,A_{N-1})$ を管理し，区間加算と区間最小値取得を行うデータ構造．

• RangeAddRangeMin<T>(n)：長さ $n$，全要素 $0$ で初期化する．
• RangeAddRangeMin<T>(a)：列 a で初期化する．
• add(l, r, x)：各 $i\in[l,r)$ について $A_i\leftarrow A_i+x$ とする．
• min(l, r) / prod(l, r)：$\min_{i\in[l,r)} A_i$ を返す．
• get(p)：$A_p$ を返す．
• all_min() / all_prod()：列全体の最小値を返す．

min(l, r) は空でない区間を要求する．

計算量

• add(l, r, x)：$O(\log N)$
• min(l, r)：$O(\log N)$
• get(p)：$O(\log N)$
• all_min()：$O(1)$

空間計算量は $N\geq 1$ で T を $N$ 個分．

仕組み

参考：省メモリな区間 add 区間 min - noshi91のメモ

全体の最小値を 1 個持ち，各内部ノードには「左部分木の最小値 $-$ 右部分木の最小値」だけを持つ．

区間加算では，再帰関数が「現在見ているノードの区間最小値の増分」を返す． 左右の増分が分かれば，保持している左右最小値差を更新でき，親の区間最小値の増分も計算できる．

このため通常の lazy segment tree と違い，各ノードに最小値と遅延値を両方持つ必要がない．

Verified with

• verify/data-structure/LC_range_add_range_min.test.cpp

Code

#pragma once

template <class T>
struct RangeAddRangeMin {
  RangeAddRangeMin() : RangeAddRangeMin(0) {}
  explicit RangeAddRangeMin(int n) : RangeAddRangeMin(vector<T>(n, T(0))) {}
  explicit RangeAddRangeMin(const vector<T>& a) : N(a.size()), root_min(T(0)), diff(max(0, N - 1), T(0)) {
    if (N > 0) root_min = build(0, 0, N, a);
  }
  void add(int l, int r, T x) {
    if (l >= r) return;
    assert(0 <= l && l <= r && r <= N);
    root_min += add(0, 0, N, l, r, x);
  }
  T min(int l, int r) const {
    assert(0 <= l && l <= r && r <= N);
    assert(l < r);
    return min(0, 0, N, l, r, root_min);
  }
  T prod(int l, int r) const { return min(l, r); }
  T get(int p) const {
    assert(0 <= p && p < N);
    return min(p, p + 1);
  }
  T all_min() const {
    assert(N > 0);
    return root_min;
  }
  T all_prod() const { return all_min(); }
  int size() const { return N; }

 private:
  int N;
  T root_min;
  vector<T> diff;
  static int internal_count(int len) { return max(0, len - 1); }
  static int right_child(int id, int l, int m) { return id + 1 + internal_count(m - l); }
  T build(int id, int l, int r, const vector<T>& a) {
    if (r - l == 1) return a[l];
    int m = (l + r) / 2;
    T ml = build(id + 1, l, m, a);
    T mr = build(right_child(id, l, m), m, r, a);
    diff[id] = ml - mr;
    return std::min(ml, mr);
  }
  T add(int id, int l, int r, int ql, int qr, T x) {
    if (qr <= l || r <= ql) return T(0);
    if (ql <= l && r <= qr) return x;
    int m = (l + r) / 2;
    int rid = right_child(id, l, m);
    T dl = add(id + 1, l, m, ql, qr, x);
    T dr = add(rid, m, r, ql, qr, x);
    T d = diff[id];
    T ret = d <= T(0) ? std::min(dl, -d + dr) : std::min(d + dl, dr);
    diff[id] = d + dl - dr;
    return ret;
  }
  T min(int id, int l, int r, int ql, int qr, T cur_min) const {
    if (qr <= l || r <= ql) return numeric_limits<T>::max();
    if (ql <= l && r <= qr) return cur_min;
    int m = (l + r) / 2;
    T d = diff[id];
    T left_min = cur_min + max(d, T(0));
    T right_min = cur_min + max(-d, T(0));
    return std::min(min(id + 1, l, m, ql, qr, left_min), min(right_child(id, l, m), m, r, ql, qr, right_min));
  }
};

/**
 * @brief Range Add Range Min
 * @docs docs/data-structure/range-add-range-min.md
 */

#line 2 "data-structure/range-add-range-min.hpp"

template <class T>
struct RangeAddRangeMin {
  RangeAddRangeMin() : RangeAddRangeMin(0) {}
  explicit RangeAddRangeMin(int n) : RangeAddRangeMin(vector<T>(n, T(0))) {}
  explicit RangeAddRangeMin(const vector<T>& a) : N(a.size()), root_min(T(0)), diff(max(0, N - 1), T(0)) {
    if (N > 0) root_min = build(0, 0, N, a);
  }
  void add(int l, int r, T x) {
    if (l >= r) return;
    assert(0 <= l && l <= r && r <= N);
    root_min += add(0, 0, N, l, r, x);
  }
  T min(int l, int r) const {
    assert(0 <= l && l <= r && r <= N);
    assert(l < r);
    return min(0, 0, N, l, r, root_min);
  }
  T prod(int l, int r) const { return min(l, r); }
  T get(int p) const {
    assert(0 <= p && p < N);
    return min(p, p + 1);
  }
  T all_min() const {
    assert(N > 0);
    return root_min;
  }
  T all_prod() const { return all_min(); }
  int size() const { return N; }

 private:
  int N;
  T root_min;
  vector<T> diff;
  static int internal_count(int len) { return max(0, len - 1); }
  static int right_child(int id, int l, int m) { return id + 1 + internal_count(m - l); }
  T build(int id, int l, int r, const vector<T>& a) {
    if (r - l == 1) return a[l];
    int m = (l + r) / 2;
    T ml = build(id + 1, l, m, a);
    T mr = build(right_child(id, l, m), m, r, a);
    diff[id] = ml - mr;
    return std::min(ml, mr);
  }
  T add(int id, int l, int r, int ql, int qr, T x) {
    if (qr <= l || r <= ql) return T(0);
    if (ql <= l && r <= qr) return x;
    int m = (l + r) / 2;
    int rid = right_child(id, l, m);
    T dl = add(id + 1, l, m, ql, qr, x);
    T dr = add(rid, m, r, ql, qr, x);
    T d = diff[id];
    T ret = d <= T(0) ? std::min(dl, -d + dr) : std::min(d + dl, dr);
    diff[id] = d + dl - dr;
    return ret;
  }
  T min(int id, int l, int r, int ql, int qr, T cur_min) const {
    if (qr <= l || r <= ql) return numeric_limits<T>::max();
    if (ql <= l && r <= qr) return cur_min;
    int m = (l + r) / 2;
    T d = diff[id];
    T left_min = cur_min + max(d, T(0));
    T right_min = cur_min + max(-d, T(0));
    return std::min(min(id + 1, l, m, ql, qr, left_min), min(right_child(id, l, m), m, r, ql, qr, right_min));
  }
};

/**
 * @brief Range Add Range Min
 * @docs docs/data-structure/range-add-range-min.md
 */

Back to top page