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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+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