累積和で範囲合計

コンピューターサイエンス理論 / 全 5 枚

コンピューターサイエンス理論 - 累積和で範囲合計

先に足しておく

区間の合計を何度も聞かれるなら、聞かれるたびに足すのは無駄です。先頭からの合計を1度だけ作っておけば、あとは引き算1回で答えが出ます。

この l === 0 の分岐を外すと何が起きるか、図解で実際に踏んでみます。

s を作るのに1周ぶん。そのあとは何回聞かれても引き算1回です。

const s = [arr[0]];
for (let i = 1; i < arr.length; i++) {
  s[i] = s[i - 1] + arr[i];
}
const sum = s[r] - (l === 0 ? 0 : s[l - 1]);

1 / 5

← → キーでも送れます