펜윅트리(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 배열을 이용해서 처음 부터 합 구하기 구현 |
1
2
3
4
5
6
7
8
9
|
int sum(int i) {
int ans = 0;
while (i > 0) {
ans += tree[i];
i -= (i & -i); //이진수에서 마지막 위치의 1을 뺀다.
}
return ans;
}
|
cs |
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 배열에 입력된 데이터 갱신하기 구현 |
1
2
3
4
5
6
7
|
void update(int i, int num) {
while (i <= n) {
tree[i] += num;
i += (i & -i); //이진수에서 마지막 위치의 1을
}
}
|
cs |
Tree 배열을 이용해서 구간합 구하기 |
A[7]~A[13] 까지의 합을 구하는 방법은
sum(13) - sum(6) 와 같이 구하면 됨
문제풀이 |
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3732&sca=5020
#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;
}
'강의자료 > 알고리즘' 카테고리의 다른 글
[자료구조] 비트마스크(bitmask)_I (10) | 2021.12.14 |
---|---|
[자료구조] 2D 펜윅트리(2차원 펜윅트리) (7) | 2021.12.09 |
[자료구조]세그먼트트리(Segment Tree) (15) | 2021.11.26 |
기하 알고리즘] 두 원의 겹치는 영역의 넓이 구하기 (9) | 2021.09.03 |
[알고리즘] Lazy Propagation 알고리즘 (6) | 2021.02.22 |