[javascript] 펜윅 트리 Fenwick tree

펜윅 트리 Fenwick tree

펜윅 트리는 주로 구간 합 계산을 수행하는데 활용되지만, 필요에 따라 다른 연산도 확장할 수 있습니다. 예를 들어, 펜윅 트리를 활용하여 업데이트와 구간 합 계산 이외에도 최솟값, 최댓값, 구간 곱 계산 등 다양한 연산을 수행할 수 있습니다.

작성자: ospace114@empal.com, http://ospace.tistory.com/

동작방식

간단한게 동작하는 방식을 살펴보습니다. 값이 0, 1, 2, 3, 4, 5, 6, 7에 대해 작성해보겠습니다.

인덱스	1	2	3	4	5	6	7	8
2진수	0001	0010	0011	0100	0101	0110	0111	1000
마지막1	1	2	1	4	1	2	1	8
저장된값	0	1	2	6	4	9	6	28

마지막1이 자신을 포함해서 앞의 합하는 개수를 의미합니다. 즉, 1은 자신 값이 되고 2는 자신과 앞에 1개가 된다. 4는 자신과 앞에 3개 값이 된다. 예를들어, 인덱스 4에는 마지막1이 4이므로 1, 2, 3, 4에 있는 값합이 저장된다. 인덱스 6는 마지막1이 2이므로 5, 6에 있는 값합이 저장된다. 인덱스 8은 앞의 1~8까지 합이 저장됩니다.

다르게 말하면 이진수 각 비트는 값의 누적 위치를 말한다. 누적합을 계산하고 싶다면 자신 비트에서 1에 위치 값을 합하면 된다. 비트가 1인 값의 개수만큼 연산이 필요하다. 예를 들어 인덱스 7는 이진수로 0111이다. 0111인 자신을 먼저 더하고 마지막 1를 제거한 0110인 인덱스 6의 값을 더한다. 다시 마지막 1을 제거한 0100인 인덱스 4에 값을 더한다. 마지막 1을 제거하면 모드 0이기 때문에 앞에 합이 인덱스 7까지의 합이 된다. 이진수가 0111이기에 모두 3개 값의 합이 된다.

값을 변경하는 경우 자신 포함 값이 영향을 받는 모든 구간을 수정해줘야 합니다. 예를 들어 인덱스 3이 수정된다면 인덱스 4와 인덱스 8에 영향을 줍니다. 이는 “i += i & -1”통해서 계산할 수 있습니다. 이 연산은 마지막1을 추출해서 더하는 작업이다.

i & -1 의미는 x에 대해 -x는 x의 비트를 반전한 후 1을 더한 값(2의 보수)이다. 이진 표현에서 가장 오른쪽에 있는 1의 비트만 남기고 나머지 비트를 모두 0으로 만듭니다. 예를 들어 i가 6이고 6은 이진수로 110이고 -6은 -110이다. “i & -i”은 “110 & (-110)”이고 결과는 “10”이 된다. 이는 십진수로 2가 된다.

자바스크립트 코드

계산의 편의를 위해 인덱스는 1에서 시작합니다.

function FenwickTree(size) {
  this.tree = new Array(size + 1).fill(0);
  this.size = size;
}
Object.assign(FenwickTree.prototype, {
  // 요소를 업데이트할 때는 해당 인덱스의 값을 증가시킵니다.
  // 이때, 인덱스의 비트를 이용하여 구간을 효율적으로 찾을 수 있습니다.
  update(idx, delta) {
    while (idx <= this.size) {
      this.tree[idx] += delta;
      idx += idx & -idx;
    }
  },
  // 구간 합을 계산할 때는 해당 인덱스부터 1까지 거슬러 올라가면서 누적 합을 계산합니다.
  // 이때, 인덱스의 비트를 이용하여 효율적으로 구간을 찾습니다.
  query(idx) {
    let ret = 0;
    while (idx > 0) {
      ret += this.tree[idx];
      idx -= idx & -idx;
    }
    return ret;
  },
  rangeQuery(l, r) {
    return this.query(r) - this.query(l - 1);
  }
});

사용예

const nums = [1, 3, 5, 7, 9];
const fenwick = new FenwickTree(nums.length);

nums.forEach((it, i) => fenwick.update(i + 1, nums[i]));

console.log(fenwick.rangeQuery(2, 4));
fenwick.update(3, 2);
console.log(fenwick.rangeQuery(2, 4));