[JS] 누적합 (Prefix Sum)

❗️누적합 알고리즘 (Prefix Sum Algorithm)

• 주어진 배열에서 인덱스 범위 내의 원소들의 합을 빠르게 계산하는 알고리즘

✅ 누적합 함수 구현

function cumulativeSum(arr){
  let cumsum = new Array(arr.length + 1).fill(0);
  for (let i = 0 ; i < arr.length; i++){
  	cumsum[i+1] = cumsum[i] + arr[i];
  }
  return cumsum;
}

❗️ 구간 합 구하기 4 - 백준 11659번

https://www.acmicpc.net/problem/11659
✅ 코드 구현

let dir = __dirname + "/11659.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);
let arr = input.shift().split(" ").map(Number);
let list = input.map((el) => el.split(" ").map(Number));

function prefixSum(arr) {
  let cumSum = Array(arr.length + 1).fill(0);

  for (let i = 0; i < arr.length; i++) {
    cumSum[i + 1] = cumSum[i] + arr[i];
  }
  return cumSum;
}

let cumSum = prefixSum(arr);

let answer = [];
list.forEach((el) => {
  let [a, b] = el;
  answer.push(cumSum[b] - cumSum[a - 1]);
});

console.log(answer.join("\n"));