Range Add Range Positive Sum
(data-structure/range-add-range-positive-sum.hpp)

• View this file on GitHub
• Last update: 2026-07-02 22:11:12+09:00
• Include: #include "data-structure/range-add-range-positive-sum.hpp"

列 $A=(A_0,A_1,\dots,A_{N-1})$ を管理し，区間加算と正の部分だけの区間和を求めるデータ構造．

• RangeAddRangePositiveSum<T>(n)：長さ $n$，全要素 $0$ で初期化する．
• RangeAddRangePositiveSum<T>(a)：列 a で初期化する．
• add(l, r, v)：各 $i\in[l,r)$ について $A_i\leftarrow A_i+v$ とする．
• sum(l, r)：$\sum_{i=l}^{r-1}\max(A_i,0)$ を返す．

空区間に対する add は何もせず，sum は $0$ を返す．

計算量

平方分割を用いる．ブロックサイズを $B$，ブロック数を $M$ とすると，

• add(l, r, v)：$O(B\log B+M)$
• sum(l, r)：$O(B+M\log B)$

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

仕組み

各ブロックについて，遅延加算値，ソート済み列，ソート済み列の prefix sum を持つ．

ブロック全体に加算するときは遅延加算値だけを更新する． ブロックの一部だけを更新するときは，元の値を直接更新して，そのブロックのソート済み列と prefix sum を作り直す．

sum でブロック全体を見るときは，ソート済み列から lower_bound(-lazy) で正になる要素を探し，prefix sum と遅延加算値からまとめて寄与を計算する．

Verified with

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

Code

#pragma once

template <class T>
struct RangeAddRangePositiveSum {
  RangeAddRangePositiveSum() {}
  RangeAddRangePositiveSum(int n) : RangeAddRangePositiveSum(vector<T>(n)) {}
  RangeAddRangePositiveSum(const vector<T>& a) : N(a.size()), B(max(1, (int)sqrt(N))), M((N + B - 1) / B), data(a), sorted(a), sorted_sum(N + M), lazy(M) {
    for (int k = 0; k < M; k++) update_block(k);
  }
  void add(int l, int r, T v) {
    if (l >= r) return;
    int bl = l / B, br = (r - 1) / B;
    if (bl == br) {
      for (int i = l; i < r; i++) data[i] += v;
      update_block(bl);
    } else {
      if (bl * B != l) {
        bl++;
        int l1 = bl * B;
        while (l < l1) data[l++] += v;
        update_block(bl - 1);
      }
      if (r < min(N, (br + 1) * B)) {
        int r1 = br * B;
        while (r1 < r) data[--r] += v;
        update_block(br--);
      }
      for (int k = bl; k <= br; k++) lazy[k] += v;
    }
  }
  T sum(int l, int r) const {
    if (l >= r) return 0;
    T ret = 0;
    int bl = l / B, br = (r - 1) / B;
    if (bl == br) {
      for (int i = l; i < r; i++) ret += sum_point(i);
    } else {
      if (bl * B != l) {
        bl++;
        int l1 = bl * B;
        while (l < l1) ret += sum_point(l++);
      }
      if (r < min(N, (br + 1) * B)) {
        int r1 = br * B;
        while (r1 < r) ret += sum_point(--r);
        br--;
      }
      for (int k = bl; k <= br; k++) ret += sum_block(k);
    }
    return ret;
  }

 private:
  int N, B, M;
  vector<T> data, sorted, sorted_sum, lazy;
  void update_block(int k) {
    int l = B * k, r = min(N, l + B);
    int sz = r - l;
    copy(data.begin() + l, data.begin() + r, sorted.begin() + l);
    sort(sorted.begin() + l, sorted.begin() + r);
    auto it = sorted_sum.begin() + l + k;
    *it = 0;
    for (int i = 0; i < sz; i++)
      *(it + i + 1) = *(it + i) + sorted[l + i];
  }
  T sum_point(int x) const { return max<T>(0, data[x] + lazy[x / B]); }
  T sum_block(int k) const {
    int l = B * k, r = min(N, l + B);
    int sz = r - l;
    auto itl = sorted.begin() + l;
    int i = lower_bound(itl, itl + sz, -lazy[k]) - itl;
    int l1 = l + k, r1 = l1 + sz;
    return sorted_sum[r1] - sorted_sum[l1 + i] + lazy[k] * (sz - i);
  }
};

/**
 * @brief Range Add Range Positive Sum
 * @docs docs/data-structure/range-add-range-positive-sum.md
 */

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

template <class T>
struct RangeAddRangePositiveSum {
  RangeAddRangePositiveSum() {}
  RangeAddRangePositiveSum(int n) : RangeAddRangePositiveSum(vector<T>(n)) {}
  RangeAddRangePositiveSum(const vector<T>& a) : N(a.size()), B(max(1, (int)sqrt(N))), M((N + B - 1) / B), data(a), sorted(a), sorted_sum(N + M), lazy(M) {
    for (int k = 0; k < M; k++) update_block(k);
  }
  void add(int l, int r, T v) {
    if (l >= r) return;
    int bl = l / B, br = (r - 1) / B;
    if (bl == br) {
      for (int i = l; i < r; i++) data[i] += v;
      update_block(bl);
    } else {
      if (bl * B != l) {
        bl++;
        int l1 = bl * B;
        while (l < l1) data[l++] += v;
        update_block(bl - 1);
      }
      if (r < min(N, (br + 1) * B)) {
        int r1 = br * B;
        while (r1 < r) data[--r] += v;
        update_block(br--);
      }
      for (int k = bl; k <= br; k++) lazy[k] += v;
    }
  }
  T sum(int l, int r) const {
    if (l >= r) return 0;
    T ret = 0;
    int bl = l / B, br = (r - 1) / B;
    if (bl == br) {
      for (int i = l; i < r; i++) ret += sum_point(i);
    } else {
      if (bl * B != l) {
        bl++;
        int l1 = bl * B;
        while (l < l1) ret += sum_point(l++);
      }
      if (r < min(N, (br + 1) * B)) {
        int r1 = br * B;
        while (r1 < r) ret += sum_point(--r);
        br--;
      }
      for (int k = bl; k <= br; k++) ret += sum_block(k);
    }
    return ret;
  }

 private:
  int N, B, M;
  vector<T> data, sorted, sorted_sum, lazy;
  void update_block(int k) {
    int l = B * k, r = min(N, l + B);
    int sz = r - l;
    copy(data.begin() + l, data.begin() + r, sorted.begin() + l);
    sort(sorted.begin() + l, sorted.begin() + r);
    auto it = sorted_sum.begin() + l + k;
    *it = 0;
    for (int i = 0; i < sz; i++)
      *(it + i + 1) = *(it + i) + sorted[l + i];
  }
  T sum_point(int x) const { return max<T>(0, data[x] + lazy[x / B]); }
  T sum_block(int k) const {
    int l = B * k, r = min(N, l + B);
    int sz = r - l;
    auto itl = sorted.begin() + l;
    int i = lower_bound(itl, itl + sz, -lazy[k]) - itl;
    int l1 = l + k, r1 = l1 + sz;
    return sorted_sum[r1] - sorted_sum[l1 + i] + lazy[k] * (sz - i);
  }
};

/**
 * @brief Range Add Range Positive Sum
 * @docs docs/data-structure/range-add-range-positive-sum.md
 */

Back to top page