累積和（1次元）

累積和とは

Σ(i = n) ^ m のクエリを高速に解くためのアルゴリズムである。 事前にΣ(i = 0) ^ m を求めておいて、これをS_mとするとS_m - S_(n - 1)が求めたい総和になる。

事前に求めるパートがO(N)であり、それ以降はO(1)でクエリをこなすことができる。

実装

let mut s = [0];
for &a in &a {
    s.push(s.last().unwrap() + a);
}

これはs[i]で[0, i)の総和を求めることができる。実装の問題でこうしているだけでunwrap_or(0)を用いることで[0, i]ともできる。自分はclosed setの方が直感的で好きです。半開区間はLebesgue積分を思い出すなあ。