JavaScript Fenwick Tree: lowbit로 구간 합과 단일 증가 갱신 구현

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

접두사 합 배열은 구간 합을 O(1)에 답하지만 원소 하나가 바뀌면 뒤쪽 합계도 모두 수정해야 합니다. 반대로 원래 배열만 두면 갱신은 빠르고 질의가 느립니다. Fenwick Tree는 길이가 2의 거듭제곱인 일부 구간 합을 저장해 두 연산을 O(log n)으로 맞춥니다. 단일 원소 증가와 합계에 집중할 때 세그먼트 트리보다 짧고 저장 공간의 상수도 작습니다.

외부 API add(index,delta)는 현재 값에 delta를 더합니다. 새 값으로 교체하는 API가 아닙니다. prefix(end)는 [0,end), sum(left,right)는 [left,right)의 합입니다. right를 포함하지 않으므로 전체 합은 sum(0,n), 빈 구간은 sum(i,i)입니다. 초기 배열은 모두 0이며 별도 값이 있으면 각 위치에 add로 넣습니다.

교육용 n 제한은 0~1,000,000입니다. Number의 비트 연산은 32비트 부호 정수로 변환하므로 무제한 큰 인덱스에 i & -i를 적용하면 안 됩니다. 이 제한에서는 갱신 경로의 다음 값도 양의 32비트 범위에 남습니다. tree의 값은 비트 연산하지 않으며 일반 Number 덧셈으로 보관합니다.

정확성을 지키는 불변식

내부 인덱스 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이 됩니다.

add는 바뀐 원소를 포함하는 저장 블록을 향해 i+=lowbit(i)로 올라갑니다. 외부 index를 내부로 바꾸지 않아 i=0에서 시작하면 lowbit(0)=0이어서 루프가 멈추지 않습니다. 이 코드가 index+1을 사용하는 핵심 이유입니다. 구간 합은 prefix(right)−prefix(left)로 앞부분을 상쇄합니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 fenwick.cjs로 저장하고 파일이 있는 폴더에서 node fenwick.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

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);
  }
}

module.exports = { Fenwick };

if (require.main === module) {
  const f = new Fenwick(4);
  [3, 1, 4, 2].forEach((value, index) => f.add(index, value));
  console.log(f.sum(1, 4));
  f.add(2, -3);
  console.log(f.sum(1, 4));
}

직접 실행 출력:

7
4

boundary는 누적 합의 끝점에 n을 허용합니다. add는 같은 검사를 재사용한 뒤 index===n만 따로 거부합니다. 조회 끝점과 원소 인덱스의 허용 범위가 다르기 때문입니다. n=0에서는 sum(0,0)만 정상이며 어떠한 add도 할 수 없습니다.

prefix의 반복문이 선택하는 블록은 길이가 서로 다를 수 있습니다. 예를 들어 end=7이면 7→6→4→0으로 이동해 길이 1,2,4 블록을 더합니다. 데이터 값이 음수라도 이동 경로는 인덱스에 의해 결정되므로 합계 질의는 그대로 동작합니다.

add에서 delta가 안전한 정수인지는 검사하지만 모든 누적값의 오버플로를 다시 계산하지는 않습니다. 호출자는 언제나 원소들의 절댓값 합과 업데이트 뒤 모든 중간 합이 Number.MAX_SAFE_INTEGER 이하라는 계약을 지켜야 합니다. 정수 범위를 벗어나는 장부에는 별도의 BigInt 합계 버전이 필요합니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

대입 갱신이 필요하면 원래 값을 별도로 보관해 delta=newValue−oldValue를 계산해야 합니다. 현재 값 대신 newValue를 그대로 add하면 중복 누적됩니다. 반대로 단일 증가만 필요한데 대입 배열까지 유지하면 불필요한 상태가 생깁니다.

구간 최솟값은 prefix(right)−prefix(left)처럼 앞부분을 취소할 수 없으므로 이 합계 코드를 단순히 Math.min으로 바꿔서는 안 됩니다. 결합 연산이 달라지거나 단일 대입·범용 구간 질의가 필요하면 세그먼트 트리를 검토하세요.

원소를 중간에 삽입해 인덱스가 밀리는 목록이나 10억 단위의 희소 좌표에는 이 배열을 그대로 할당하지 마세요. 좌표가 사전에 알려졌다면 좌표 압축을 먼저 할 수 있습니다. 음수가 포함된 합계는 지원하지만 누적합이 단조임을 이용하는 k번째 원소 탐색은 이 글의 범위가 아닙니다.

연습으로 확인하기

처음 0인 선반 장부에 보정량이 들어올 때마다 특정 구간의 순합을 반환해 보세요. 음수 보정과 빈 구간을 넣으면 인덱스 계약을 제대로 이해했는지 드러납니다.

[창작 문제] 분산 선반의 보정 장부

AtCoder B – Fenwick Tree — 단일 증가와 구간 합을 다루는 공식 연습입니다. 외부 문제의 입력 규모와 숫자 범위를 별도로 확인하고 구현의 Number 계약과 비교하세요.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• AtCoder Library 공식 Fenwick Tree 문서
• MDN Bitwise AND: Number의 32비트 변환
• AtCoder B – Fenwick Tree