코딩테스트 JS Fenwick Tree: 값 갱신과 구간 합 처리

Node.js 24 CommonJS용 전체 풀이입니다. fenwick-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 .input.json | node .fenwick-problem.cjs

macOS / Linux:
node fenwick-problem.cjs < input.json

class Fenwick {
  constructor(n) {
    if (!Number.isInteger(n) || n < 0 || n > 1_000_000) {
      throw new RangeError('n은 0~1,000,000 정수여야 합니다.');
    }
    this.n = n;
    this.tree = Array(n + 1).fill(0);
  }
  boundary(i) {
    if (!Number.isInteger(i) || i < 0 || i > this.n) {
      throw new RangeError('경계는 0~n 정수여야 합니다.');
    }
  }
  add(index, delta) {
    this.boundary(index);
    if (index === this.n) throw new RangeError('갱신 인덱스는 n보다 작아야 합니다.');
    if (!Number.isSafeInteger(delta)) throw new TypeError('증가량은 안전한 정수여야 합니다.');
    for (let i = index + 1; i <= this.n; i += i & -i) {
      this.tree[i] += delta;
    }
  }
  prefix(end) {
    this.boundary(end);
    let sum = 0;
    for (let i = end; i > 0; i -= i & -i) sum += this.tree[i];
    return sum;
  }
  sum(left, right) {
    this.boundary(left);
    this.boundary(right);
    if (left > right) throw new RangeError('left는 right 이하여야 합니다.');
    return this.prefix(right) - this.prefix(left);
  }
}

function solve({ n, ops }) {
  const f = new Fenwick(n), out = [];
  for (const [type, a, b] of ops) {
    if (type === 'add') f.add(a, b);
    else if (type === 'sum') out.push(f.sum(a, b));
    else throw new Error('알 수 없는 작업입니다.');
  }
  return out;
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

처음 두 add 뒤 장부는 [3,0,5,0]입니다. [0,3)의 합은 8입니다. 2번 선반에 −2를 더하면 [3,0,3,0]이 되고 [1,4)의 합은 3입니다. [2,2)는 어떤 원소도 포함하지 않습니다. solve의 분기에서 add는 출력하지 않고 sum만 out에 추가하는 것이 출력 개수를 맞추는 핵심입니다.

내부 인덱스 i는 외부 index+1입니다. lowbit(i)=i & -i는 가장 낮은 1비트의 값입니다. tree[i]는 내부 [i−lowbit(i)+1,i]의 합을 저장합니다. i=6이면 lowbit=2이므로 내부 5,6번 두 원소의 합을 보관합니다. 같은 구간을 무작정 겹쳐 더하는 것이 아니라 질의 때 서로 겹치지 않게 선택합니다.

prefix(end)는 내부 i=end에서 시작합니다. tree[i]를 더한 뒤 i−=lowbit(i)로 방금 더한 블록을 건너뛰면 아직 더하지 않은 앞부분만 남습니다. 끝의 1비트를 하나씩 없애므로 O(log n)개 블록 뒤 0이 됩니다.

초기 배열 O(n), q개 작업 최악 O(q log(n+1)), 구조 O(n+1)와 결과 O(q) 공간입니다. 입력 JSON과 ops 자체도 O(q) 공간을 차지하며 스트리밍 입력 구현은 아닙니다.

표본과 경계를 직접 확인하려면 다음 코드를 fenwick-check.cjs로 저장하고 같은 폴더에서 node fenwick-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./fenwick-problem.cjs');

assert.deepEqual(
  solve({
  "n": 4,
  "ops": [
    [
      "add",
      0,
      3
    ],
    [
      "add",
      2,
      5
    ],
    [
      "sum",
      0,
      3
    ],
    [
      "add",
      2,
      -2
    ],
    [
      "sum",
      1,
      4
    ],
    [
      "sum",
      2,
      2
    ]
  ]
}),
  [8,3,0],
);
assert.deepEqual(
  solve({
  "n": 0,
  "ops": [
    [
      "sum",
      0,
      0
    ]
  ]
}),
  [0],
);