C++의 이진 인덱스 트리 또는 Fenwick 트리?

평평한 숫자 배열과 비교하는 경우 Fenwick 트리는 요소 업데이트와 접두사 합계 계산이라는 두 가지 작업 간의 균형이 훨씬 더 좋습니다. m개의 숫자로 구성된 평면 배열의 경우 요소를 저장하거나 접두사 합계를 저장할 수 있습니다. 첫 번째 경우 접두사 합계를 계산하는 데 선형 시간이 필요합니다. 두 번째 인스턴스의 경우 배열 요소를 수정하거나 업데이트하는 데 선형 시간이 필요합니다(두 인스턴스 모두에서 다른 작업은 일정한 시간에 완료될 수 있음). Fenwick 트리를 사용하면 O(log m) 시간에 두 작업을 모두 수행할 수 있습니다. 이것은 각 노드의 값이 해당 하위 트리에 있는 숫자의 합으로 처리되는 트리로 숫자를 표시하여 얻습니다. 트리 구조는 O(log m) 노드 액세스만 사용하여 작업을 수행할 수 있도록 합니다.

1 기반 배열을 고려하면 Fenwick 트리를 가장 쉽게 이해할 수 있습니다. 인덱스 j가 2의 거듭제곱인 각 요소에는 첫 번째 j 요소의 합이 포함됩니다. 인덱스가 2의 2승(고유)의 합을 나타내는 요소는 이전 2의 거듭제곱 이후 요소의 합으로 구성됩니다. 기본적으로 각 요소는 트리에서 부모 이후 값의 합으로 구성되며 해당 부모는 인덱스에서 최소 또는 최하위 비트를 지워서 찾았습니다.

주어진 위치 또는 인덱스까지 합을 계산하려면 위치 또는 인덱스의 이진 확장을 고려하고 각 1비트에 해당하는 요소를 이진 형식으로 추가합니다.

예를 들어 처음 11개 값의 합을 계산하려고 한다고 가정해 보겠습니다. 11은 2진수로 1011입니다. 이것은 3개의 1비트로 구성되므로 1000, 1010 및 1011의 세 가지 요소를 추가해야 합니다. 이들은 각각 값 1-8, 9-10 및 11의 합계로 구성됩니다.

간단한 C 구현은 다음과 같습니다.

예시

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}