[javascript] 비트 트리 (Binary Indexed Tree) 데이터 구조

08 Dec 2023

javascript

비트 트리 (Binary Indexed Tree)는 효율적인 구간 합 계산을 지원하는 데이터 구조입니다. 이 구조는 주로 배열의 각 요소를 로그 시간에 조작할 수 있는 상황에서 유용합니다.

이 포스트에서는 비트 트리의 개념과 구현에 대해 소개하고자 합니다. 마지막으로, 비트 트리를 사용하여 구간 합을 계산하는 예시를 제시할 것입니다.

개념

비트 트리는 배열의 각 요소를 효율적으로 조작하기 위한 목적으로 설계되었습니다. 주로 합과 같은 연산을 빠르게 수행해야 하는 상황에서 사용됩니다. 비트 트리는 0이 아닌 마지막 비트를 찾는 방법에 따라 다양한 방식으로 구현될 수 있습니다. 크게 Fenwick Tree라고도 불리며, O(log n) 시간 복잡도로 각 요소의 값을 결합하고 수정할 수 있는 효율적인 방법을 제공합니다.

구현

비트 트리의 구현은 간단합니다. 각 요소를 조작하기 위한 배열을 초기화한 뒤, 정해진 규칙에 따라 인덱스를 조절하여 특정 구간의 합을 계산하거나 요소를 수정합니다.

아래는 JavaScript를 사용하여 비트 트리를 구현하는 예제코드입니다.

class BinaryIndexedTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, value) {
    while (index <= this.size) {
      this.tree[index] += value;
      index += index & -index;
    }
  }

  query(index) {
    let sum = 0;
    while (index > 0) {
      sum += this.tree[index];
      index -= index & -index;
    }
    return sum;
  }
}

// Usage
const BIT = new BinaryIndexedTree(5);
BIT.update(1, 2);
BIT.update(2, 3);
console.log(BIT.query(2)); // Output: 5

구간 합 계산

구간 합을 계산하기 위해서는 특정 범위의 인덱스에 대한 합을 계산하고 반환하는 query 메서드를 사용합니다. 이 메서드는 배열의 누적 합을 이용하여 구간 합을 효율적으로 계산합니다.

결론

비트 트리는 구간 합을 효율적으로 계산하기 위한 유용한 데이터 구조입니다. 이를 통해 배열의 각 요소에 대한 조작을 로그 시간에 수행할 수 있습니다. 따라서 비트 트리는 알고리즘 문제나 실제 문제 해결에 유용하게 활용됩니다.

이상으로 비트 트리에 대한 개념과 구현, 그리고 구간 합 계산에 대해 알아보았습니다. 부족한 내용이 있다면 추가로 살펴보시기를 권장드립니다.

목차

개념

구현

구간 합 계산

결론