[백준12837_자바스크립트(javascript)] - 가계부 (Hard)

🔴 문제

가계부 (Hard)

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, _] = inputs.shift();
const tree = Array(4 * n).fill(0);

const update = (start, end, node, idx, diff) => {
  if (idx < start || end < idx) return;

  tree[node] += diff;

  if (start === end) return;

  const mid = Math.floor((start + end) / 2);

  update(start, mid, 2 * node, idx, diff);
  update(mid + 1, end, 2 * node + 1, idx, diff);
};

const sum = (start, end, node, left, right) => {
  if (right < start || end < left) return 0;

  if (left <= start && end <= right) return tree[node];

  const mid = Math.floor((start + end) / 2);
  return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
};

for (const [query, p, q] of inputs) {
  if (query === 1) update(0, n - 1, 1, p - 1, q);
  if (query === 2) console.log(sum(0, n - 1, 1, p - 1, q - 1));
}

🟢 풀이

⏰ 소요한 시간 : -

입력의 형태가 딱 세그먼트 트리..!
세그먼트트리의 기본형이라 무난하게 풀이했다.

이 문제는 init 함수없이 4n 크기의 트리를 0으로 초기화 하면된다.
이 상태에서 쿼리가 1로 들어오면 업데이트 함수를 통해 p번째 구간합에 포함된 모든 노드를 diff만큼 변경시키면 된다.
쿼리가 2라면 p부터 q까지의 구간합을 구하면 된다.

이 풀이가 이해되지 않으면 구간 합 구하기 문제를
먼저 풀고, 풀이를 보고오는것을 추천한다.

🔵 Ref