ei1333's page

一次元累積和

説明

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

使い方

• set(k, x): 要素 $k$ に値 $x$ を加える
• build(): 累積和を構築する

• query(k): 区間 $[0, k]$ の和を求める

計算量

• build: $O(n)$
• add, query: $O(1)$

実装例

問題例