一次元累積和(Cumulative-Sum)

説明

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

計算量

• 構築 $O(N)$
• クエリ $O(1)$

実装例

• add($k$, $x$): 要素 $k$ に値 $x$ を加える
• build(): 累積和を構築する
• query($k$): 区間 $[0, k]$ の和を求める(閉区間なので注意)

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

  CumulativeSum(int sz) : data(sz, 0) {};

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

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

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