1 次元累積和

説明

1 次元の累積和

---

情報

項目	データ
計算量	構築 $O(N)$ クエリ $O(1)$

関数

CumulativeSum(sz)
機能	サイズ $sz$ で初期化
引数	$sz$: 大きさ

void add(k, x)
機能	$k$ 番目の要素に $x$ を足す
引数	$k$: 要素位置(0 - indexed)
	$x$: 値

void build()
機能	構築

int query(k)
機能	$[0, k]$の和を求める
引数	$k$: 和の右端
戻り値	和

実装例