[자료구조] 펜윅트리(Fenwick Tree)

펜윅트리(Fenwick Tree)란?

- Binary Indexed Tree 라고도 하며 이진수를 이용하여 위치값을 표현하는 세그먼트 트리와 유사한 트리

 

펜윅트리(Fenwick Tree) 의 개념

10진수 수를 이진수로 표현해 보면 다음과 같다.

3 =  00000011
4 =  00000100
5 =  00000101
6 =  00000110
8 =  00001000
9 =  00001001
10 = 00001010
11 = 00001011
12 = 00001100
16 = 00010000

여기서 이진수의 마지막 1의 위치를 확인하면 다음과 같다.

3= 왼쪽에서 첫번째 자리 (10진수의 값으로 1)

4= 왼쪽에서 3번째 자리 (10진수의 값으로 4)

5= 왼쪽에서 첫번째 자리(10진수의 값으로 1)

...

16 = 왼쪽에서 5번째 자리(10진수의 값으로 16)

이러한 값을 저장하는 L[i]라고 표현 한다고 하면

L[3]=1,L[4]=4,L[5]=1,....,L[16]=16 이라고 표현할 수 있다.

수 N개를 A[1]~A[N] 이라고 했을 때 Tree[i]는 A[i] 부터 앞 방향으로 L[i]개의 합을 저장한다.

그림으로 살펴 보면 다음과 같다.

여기서

Tree[1] 에는 A[1]~A[1] 까지의 합

Tree[2] 에는 A[1]~A[2] 까지의 합

Tree[3] 에는 A[3]~A[3] 까지의 합

...

Tree[8] 에는 A[1]~A[8] 까지의 합

과 같은 형태로 저장이 된다.

 

합의 갯수 L[i] 를 구하는 방법

L[i] = i & -i

※ -i 의 값은 ~i + 1 과 같다.(음수는 2의 보수의 값을 취한다. 2의 보수는 1의 보수 + 1)

예) 

i = 100110101110101100000000000

~i = 011001010001010011111111111

-i =  011001010001010100000000000

i & -i = 000000000000000100000000000

따라서 왼쪽에서 첫번째 나오는 자리의 위치 값을 구할 수 가 있게 된다.

 

Tree[i] 에 값을 저장하는 방법

A = [3, 2, 5, 7, 10, 3, 2, 7, 8, 2, 1, 9, 5, 10, 7, 4]

Tree[8] 에는 A[1]~A[8] 까지의 합 39가 저장된다.

 

Tree 배열을 이용해서 처음 부터 합 구하기

A[1]+A[2]+...+A[13] 의 값을 구해 보자.

위의 표에서 확인을 해 보면 Tree[8] + Tree[12] + Tree[13] 인 것을 확인 할 수 있다.

13을 이진수로 나타내면 1101 이다.

여기서 Tree[1101] + Tree[1100] + Tree[1000] 인것을 알 수 있다.

즉 마지막 1의 위치를 없애면서 해당 위치의 Tree 값을 누적해 가는 원리이다.

마지막 위치의 1을 없애는 방법

i = i - (i & -i) /// 현재 i 의 위치에서 마지막 1의 위치의 값을 빼면 마지막 위치의 1이 없어진다.

 

 

Tree 배열을 이용해서 처음 부터 합 구하기 구현

 

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);  //이진수에서 마지막 위치의 1을 뺀다.
    }
    return ans;
}
 

 

 

Tree 배열에 입력된 데이터 갱신하기

 

그림에서 A[5]이 갱신되면 Tree[5],Tree[6],Tree[8],Tree[16] 의 값을 갱신해 주어야 한다.

이진수로 표현하면 5은 0101 이고

6번지는 0110

8번지는 1000

16번지는 10000

번지수를 확인해 보면 마지막 위치의 1의 자리에 1을 더해 주면 되는 원리이다.

0101 + 0001 = 0110

0110 + 0010 = 1000

1000 + 1000 = 10000

위와 같은 원리로 찾아가는 번지는 i = i + (i & -i) 와 같다.

 

Tree 배열에 입력된 데이터 갱신하기 구현

void update(int i, int num) {
    while (i <= n) {
        tree[i] += num;
        i += (i & -i); //이진수에서 마지막 위치의 1을
    }
}
 

 

 

Tree 배열을 이용해서 구간합 구하기

A[7]~A[13] 까지의 합을 구하는 방법은

sum(13) - sum(6) 와 같이 구하면 됨

 

 

문제풀이

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3732&sca=5020 

JUNGOL

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>

using namespace std;

int n,m;
int arr[500000];
long long t[1050000];

long long Sum(int index)
{
    long long res=0;
    while(index > 0)
    {
        res+=t[index];
        index -= (index & -index);
    }
    return res;
}
void Update(int index,int val)
{
    while(index <= n)
    {
        if(index> 1050000) break;
        t[index] += val;
        index += (index & -index);
    }
}

int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;i++)
    {
        scanf("%d",&arr[i]);
        Update(i, arr[i]);
    }
    for(i = 0;i < m;i++)
    {
        int s1,e1,t1;
        int s2,e2,t2;
        scanf("%d %d %d",&s1,&t1,&e1);
        scanf("%d %d %d",&s2,&t2,&e2);
        long long tot1 = Sum(e1) - Sum(s1-1);
        long long tot2 = Sum(e2) - Sum(s2-1);
        if(tot1 > tot2)
        {
            int change = (int)round(arr[t2]/2.0);
            arr[t1] += change;
            arr[t2] -= change;
            Update(t1,change);
            Update(t2,-change);
        }
        else if(tot2 > tot1)
        {
            int change = (int)round(arr[t1]/2.0);
            arr[t2] += change;
            arr[t1] -= change;
            Update(t1,-change);
            Update(t2,change);
        }
    }
    for(i = 1;i <= n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}