카테고리

티스토리 뷰

개발/Data Structure

펜윅 트리(Fenwick Tree, Binary Indexed Tree)

미누시 2019. 11. 5. 01:58

펜윅 트리는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 위키피디아에서는 다음과 같이 정의하고 있습니다 :

펜윅 트리 또는 바이너리 인덱스드 트리 는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 1989년 Boris Ryabko에 의해 처음 제안되었으며 1992년 추가로 수정되었습니다. 펜윅 트리는 Peter Fenwick에서 이름이 유래하였습니다.

일반 배열과 비교했을 때 구간 합에 대해 배열은 선형 시간이 필요하며, 이는 배열 요소를 업데이트하는 데에도 똑같이 적용됩니다. 펜윅 트리는 두 가지 작업 모두에 대해 O(log n) 시간에 수행할 수 있습니다.

 

이러한 자료구조 필요한 이유는 다음 상황들에 대해 효율적으로 처리할 수 있기 때문입니다.

  • 배열의 1번째 요소에서부터 100만번째 요소까지의 합을 구하라.
  • 배열의 10만번째 요소에서 15만번째 요소의 값에 임의의 수를 더하고 1번째 요소에서 50만번째 요소까지의 합을 구하라.

 

위 두 상황에 대해서 약 165만번의 접근을 필요로 합니다(O(n)). 펜윅 트리를 사용하면 이러한 접근들에 대해서 O(log n) 에서 수행할 수 있습니다.

 

 

 

VS 세그먼트 트리

펜윅 트리와 세그먼트 트리 모두 구간 합을 빠르게 구하기 위한 자료구조입니다. 하지만, 펜윅 트리는 세그먼트 트리의 메모리를 더 절약하기 위해 만든 방법으로, 실제로 코드도 매우 간결합니다. 아래는 같은 구간합을 세그먼트 트리와 펜윅 트리로 도식화한 그림입니다.

그림1. 세그먼트 트리
그림2. 펜윅 트리

 

 

 

펜윅트리의 구조

펜윅 트리는 구현할 때 힙을 구현할 때처럼 N크기의 배열로 구현할 수 있습니다. 이 때 편의성을 위해 0번 인덱스는 사용하지 않습니다. 배열의 크기가 10이라고 가정하면, 펜윅트리의 구조는 다음과 같이 구성할 수 있습니다.

그림3. N=10에서의 펜윅 트리

 

이 때 펜윅 트리의 구간합 구성은 다음과 같습니다 :

그림4. N=10에서의 펜윅 트리 구간합

 

펜윅트리의 i번째 요소가 의미하는 것은 아래의 규칙에 따라서 결정됩니다 :

  • 인덱스가 홀수이면, 원본 배열의 값이랑 동일하게 가집니다.
    • data[2i + 1] = arr[2i + 1]
    • data[1] = arr[1], data[3] = arr[3], data[5] = arr[5]...
  • 인덱스가 2^k의 배수를 만족하면서 2^(k+1)을 만족하지 않을 때, 해당 인덱스는 자기 자신을 포함하여 직전의 2^k개의 값의 합을 저장합니다.
    • data[12]는 2^2의 배수이면서 2^3의 배수가 아니므로 arr[9] + arr[10] + arr[11] + arr[12]의 값을 저장한다.

 

 

구간 합 구하기

구간 합을 구하는 것은 그렇게 어렵지 않습니다.

  • 구간 3 ~ 12 까지의 합 구하기 : arr[3] + ... + arr[12] = data[12] + data[8] - data[2]
  • 구간 1 ~ 7 까지의 합 구하기 : arr[1] + ... + arr[7] = data[4] + data[6] + data[7]

 

눈으로 구간합의 구성을 보고 구하니 단지 끼워 맞추기만 하면 됩니다. 하지만 이것을 어떻게 코드로 구현할 수 있을까요? 이 때 비트 연산을 사용하여 구현을 쉽게 할 수 있습니다. 위의 예로 들겠습니다 :

  1. 구간 3 ~ 12까지의 합 구하기
    • arr[1...12] = data[12] + data[8]
    • 12를 이진법으로 나타내면 1100(2)입니다.
    • 12의 가장 작은 1로 표시된 비트를 0으로 바꿉니다. 1000(2) = 8입니다. 이로써 1 ~ 12의 합은 data[12] + data[8]임을 알 수 있습니다.
    • arr[1...2] = data[2] 이므로 둘을 이제 빼면 3 ~ 12의 구간합이 나옵니다.
    • 비트 1을 0으로 바꾸는 작업은 모든 비트가 0이 될 때까지 수행하면 됩니다.
  2. 구간 1 ~ 43까지의 합 구하기
    • arr[1...43] = data[32] + data[40] + data[42] + data[43]
    • 43을 이진법으로 나타내면 101011(2)입니다.
    • 43의 가장 작은 1로 표시된 비트를 0으로 바꿉니다 -> 101010(2) = 42입니다.
    • 다음 가장 작은 1로 표시된 비트를 0으로 바꿉니다 -> 101000(2) = 40입니다.
    • 다음 가장 작은 1로 표시된 비트를 0으로 바꿉니다 -> 100000(2) = 32입니다.
    • arr[1...43] = data[43] + data[42] + data[40] + data[32]임을 알 수 있습니다.

 

위 구현은 idx &= idx - 1 연산을 idx가 0이 될 때까지 수행하면 됩니다. 구간 합 구하기의 시간복잡도는 O(log n) 임을 알 수 있습니다.

 

 

 

값 업데이트

길이가 10인 배열의 인덱스 7번의 요소의 값이 업데이트 되면, 아래 그림처럼 펜윅 트리가 업데이트되어야 합니다.

그림5. 펜윅트리 값 갱신

 

여기서 7, 8, 16번째 인덱스가 영향을 받는 것을 알 수 있습니다. 이것의 기준은 어떻게 구할 수 있을까요? 답은 가장 작은 1로 표시된 비트에 1을 더하는 것입니다.

  1. 인덱스 7 업데이트
    • 00111(2) = 7
    • 00111(2) + 00001(2) = 01000(2) = 8
    • 01000(2) + 01000(2) = 10000(2) = 16

 

 

 

구현

설명에 비해 구현은 턱없이 쉽습니다. 아래 코드를 첨부합니다 :

#include <iostream>
#include <vector>

using namespace std;

/* int형 배열에 대한 펜윅 트리 */
class Fenwick
{
public:
    /* 배열이 0 인덱스도 사용한다는 것을 가정하고 초기화하는 모습입니다. */
    Fenwick(vector<int>& Array)
    {
        Tree.resize(Array.size() + 1);
        Tree[0] = 0;
        for (int i = 1; i <= Array.size(); ++i)
            Update(i, Array[i-1]);
    }

    int Sum(int Index)
    {
        int Answer = 0;
        while (Index > 0)
        {
            Answer += Tree[Index];
            Index &= Index - 1;
        }

        return Answer;
    }

    int Sum(int Left, int Right)
    {
        return Sum(Right) - Sum(Left - 1);
    }

    void Update(int Index, int Diff)
    {
        while (Index < Tree.size())
        {
            Tree[Index] += Diff;
            Index += (Index & -Index);
        }
    }

private:
    vector<int> Tree;
};


#pragma warning(disable:4996)
int main()
{
    int N, min, max;
    cin >> N >> min >> max;

    vector<int> arr;
    for (int i = 1; i <= N; ++i)
        arr.push_back(i);

    Fenwick fenwick(arr);
    cout << fenwick.Sum(min, max) << "\n";

    return 0;
}

 

 

 

 

복잡도

  • 시간복잡도 : O(MlogN) (이 때 N은 원소의 수, M은 연산의 수입니다.)
    • 구간 합 계산 : O(logN)
    • 값 갱신 : O(logN)
  • 공간복잡도 : O(N)

 

 

 

2차원 펜윅트리

펜윅트리는 2차원에 대해서도 응용할 수 있습니다. 이 때 2차원 펜윅트리는 단순히 1차원 배열을 여러 개 이어 붙인 것으로 생각할 수 있습니다.

 

2차원에서 구간합을 계산하기 위해서는 이제 2개의 인덱스(행, 열)를 필요로 합니다. 만약, 2차원 인덱스가 3,5라면 구간합은 (1,1)(1,2)(1,3)(1,4)(1,5) ... (3,1)(3,2)(3,3)(3,4)(3,5) 인덱스의 합을 의미하게 됩니다. 이것을 구하기 위해서는 기존의 구간합 적용을 행과 열 모두에 적용하면 되며, 그 후 필요없는 인덱스를 제외하면 됩니다. 

 

그림으로 보자면 구간합은 다음과 같이 계산됩니다.

그림6. 2차원 펜윅 트리의 구간합 계산 방법

갱신 역시 행과 렬에 대해서 기존의 갱신 방식을 확장하여 사용하면 됩니다. 위의 설명에 따라 2차원 펜윅트리를 구현한 구현체는 다음과 같습니다 :

#include <iostream>
#include <vector>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#include <chrono>
#include "Utility.h"

chrono::system_clock::time_point Start;
chrono::nanoseconds Time;
#endif


class Fenwick2D
{
public:
	Fenwick2D(int N) : Size(N)
	{
		Tree = vector<vector<long long>>(Size + 1, vector<long long>(Size + 1));
	}

	long long Sum(int R, int C)
	{
		long long Answer = 0;
		int TempC;

		while (R > 0)
		{
			TempC = C;
			while (TempC > 0)
			{
				Answer += Tree[R][TempC];
				TempC -= TempC & -TempC;
			}
			R -= (R & -R);
		}
		return Answer;
	}

	long long Sum(int RLeft, int CLeft, int RRight, int CRight)
	{
		return Sum(RRight, CRight) - Sum(RLeft - 1, CRight)
			- Sum(RRight, CLeft - 1) + Sum(RLeft - 1, CLeft - 1);
	}

	void Update(int RIndex, int CIndex, long long Value)
	{
		long long Diff = Value - Sum(RIndex, CIndex, RIndex, CIndex);
		int TempC;
		while (RIndex <= Size)
		{
			TempC = CIndex;
			while (TempC <= Size)
			{
				Tree[RIndex][TempC] += Diff;
				TempC += TempC & -TempC;
			}
			RIndex += RIndex & -RIndex;
		}
	}

private:
	vector<vector<long long>> Tree;
	int Size;
};



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;
	
	int Array[1025][1025];
    // 2차원 배열에 입력 받기
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			cin >> Array[i][j];

	int Op;
	int R, C, Value, R1, C1;
	Fenwick2D Fenwick(N);
    
    // 2차원 배열을 바탕으로 펜윅 트리 초기화
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			Fenwick.Update(i, j, Array[i][j]);

	// 펜윅 트리 출력
	for (int i = 1; i <= N; ++i)
    	for (int j = 1; j <= N; ++j)
        	cout << Fenwick.Sum(i,j) << "\n";
}

 

 

복잡도

2차원 펜윅트리의 복잡도는 다음과 같습니다 :

  • N X M 행렬에 대해,
    • 구간 합 계산 : O(logMN)
    • 값 갱신 : O(logMN)
  • 공간복잡도 : O(MN)

 

 

 

레퍼런스

참고 문헌
위키피디아 - Fenwick Tree
github.io - 펜윅트리(Fenwick Tree, Binary Indexed Tree, BIT
Crocus - 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT
更上一屋樓, 한층 더 - 펜윅트리(Fenwick Tree)란?
OpenGenus IQ: Learn Computer Science

 

참고 그림
그림1, 그림2
그림3, 그림4, 그림5
그림6

저작자표시 비영리 변경금지

'개발 > Data Structure' 카테고리의 다른 글

세그먼트 트리(Segment Tree, Index Tree)  (0) 2020.04.25
댓글