累積和
その要素までの累積和の配列を作る
初期値を{ sum: 0, result: [] }のような形にすることで、O(N)で畳み込みで計算できる
code:example.ts
cumlativeSums(0,1,2,3,4,5) // 0,1,3,6,10,15 code:ts
export const cumulativeSums = (nums: number[]) => {
type _ = { sum: number; result: number[] };
return nums.reduce(
(acc: _, cur) => {
const sum = acc.sum + cur;
},
{ sum: 0, result: [] }
).result;
};
競プロであるあるらしい
よく問題になるのは、「ある配列内の任意の区間での和」を求めること
それを求めるためには、前処理として、
$ s[i]=a[0]+a[1]+⋯+a[i] とした、配列$ s(元の配列aと同じ長さ)が必要
累積和のアルゴリズムを多次元，多次数に拡張したもので