Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

使い方

計算量

Verified with

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