Cumulative Sum(一次元累積和)
(dp/cumulative-sum.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "dp/cumulative-sum.hpp"

概要

$1$ 次元の累積和. 前計算として事前に累積和をとることで, 区間の和を $O(1)$ で求めることが出来る.

使い方

• add(k, x): 要素 k に値 x を加える.
• build(): 累積和を構築する.
• fold(r): 区間 $[0, k)$ の和を返す.
• fold(l, r): 区間 $[l, r)$ の和を返す.

計算量

• add(k, x): $O(1)$
• build(): $O(N)$
• fold(r): $O(1)$
• fold(l, r): $O(1)$

Verified with

• test/verify/yosupo-static-range-sum.test.cpp

Code

template< class T >
struct CumulativeSum {
  vector< T > data;

  CumulativeSum() = default;

  explicit CumulativeSum(size_t sz) : data(sz + 1, 0) {}

  void add(int k, const T &x) {
    data[k + 1] += x;
  }

  void build() {
    for(int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  T fold(int r) const {
    if(r < 0) return 0;
    return data[min(r, (int) data.size() - 1)];
  }

  T fold(int l, int r) const {
    return fold(r) - fold(l);
  }
};

#line 1 "dp/cumulative-sum.hpp"
template< class T >
struct CumulativeSum {
  vector< T > data;

  CumulativeSum() = default;

  explicit CumulativeSum(size_t sz) : data(sz + 1, 0) {}

  void add(int k, const T &x) {
    data[k + 1] += x;
  }

  void build() {
    for(int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  T fold(int r) const {
    if(r < 0) return 0;
    return data[min(r, (int) data.size() - 1)];
  }

  T fold(int l, int r) const {
    return fold(r) - fold(l);
  }
};

Back to top page