먼저 알아야 할 것 |
펜윅트리는 세그먼트 트리에서 응용된 자료구조이며, 더 간단하고 더 적은 메모리로 연산을 처리하는 자료구조이다.
그러므로 세그먼트 트리를 먼저 공부해야 이해하기 쉽다.
https://smallpants.tistory.com/123
세그먼트 트리(Segment Tree)
세그먼트 트리란? 구간을 저장하기 위한 트리 7칸짜리 배열이 있다고 할때 0 ~ 7번째 자리에 들어있는 값들을 트리의 말단노드인 리프에 놓고 0~1번 인덱스 값의 합을 부모노드에, 2~3번 인텍스 값
smallpants.tistory.com
https://yabmoons.tistory.com/431
[ 세그먼트 트리(Segment Tree) ] 개념과 구현방법 (C++)
이번 글에서는 세그먼트 트리(Segment Tree) 에 대해서 이야기를 해보자. 1. 세그먼트 트리 ( Segment Tree ) ??가장 먼저, 세그먼트 트리가 무엇을 하기 위한 놈인지 부터 알아보자.세그먼트 트리는 "구간
yabmoons.tistory.com
펜윅트리(FenwickTree) |
세그먼트 트리와 마찬가지로 구간에 대한 연산을 빠르게 진행하기 위해 구현된 자료구조
세그먼트트리보다 메모리 소모량이 적고, 코드도 훨씬 간단하다.
먼저 세그먼트 트리의 모습은 왼쪽과 같다.
빨간글씨는 노드의 번호이며
원 안의 글씨는 배열의 인덱스이다.
세그먼트 트리를 공부하고 왔다면 바로 이해될 것이고
반면 펜윅트리는 아래와 같은 모습이다.
펜윅트리의 모습인데 트리의 형태라기보다는 조각난 표에 가까운 듯 하다.
빨간글씨는 노드의 번호이며
사각형 안의 글씨는 배열의 인덱스이다.
홀수번째 index에는 배열의 값이 그대로 저장되고
짝수번째에는 구간합들이 저장되는 형태이다.
펜윅트리 구현 방식 |
요약
1) 크기가 N인 배열을 펜윅트리로 구현한다면 펜윅트리의 크기 또한 N이다
2) 0번인덱스는 사용하지 않고 1번인덱스부터 사용한다.
3) 펜윅트리는 비트를 이용해서 생성한다.
설명
세그먼트트리와 달리 펜윅트리는 필요한 공간이 배열의 크기와 같다.
즉 배열의 크기가 N이라면 펜윅트리의 크기도 N이다.
세그먼트트리와 마찬가지로 0번인덱스는 사용하지 않고 1번부터 사용한다.
다만 이유가 다른데 세그먼트트리는 노드의 번호를 계산하기 쉽게 하려고 0번을 사용하지 않았었지만
펜윅트리는 비트연산을 위해 0번인덱스를 사용하지 않는다.
펜윅트리는 비트연산으로 진행하기 때문에 코드가 간결하다.
0과 1로 이루어진 비트에서 1의 위치를 가지고 연산을 진행한다.
그러므로 0000000보다는 0000001이 시작점으로 삼기 쉽기때문에 0번인덱스를 사용하지 않고 1번부터 사용한다.
세그먼트트리는 구간합을 중점에 두고 구현되었지만
펜윅트리는 누적합의 개념을 이용해 구현된다.
펜윅트리 만드는 법 |
펜윅트리는 비트를 이용하며 누적합 개념을 이용한다.
위와 같은 펜윅트리가 있을 때 한눈에 보기에 홀수번째 인덱스는 배열의 값을 그대로 가지고, 짝수번째 인덱스는 구간의 합을 가진다는것을 눈치 챌 수 있다.
하지만 좀 더 정확히 말한다면 1이 존재하는 최하위 비트 값을 이용해 값을 저장한다.
각 인덱스를 2진수로 표현한 표인데 펜윅트리는 1이 존재하는 최하위 비트값을 이용하는데 예를들어
2는 0010인데 가장 오른쪽에 있는 1은 숫자2를 의미한다.
3은 0011인데 가장 오른쪽에 있는 1은 숫자 1을 의미한다.
8은 1000인데 가장 오른쪽에 있는 1은 숫자 8을 의미한다.
즉 2번인덱스에는 2개의 구간합이 저장되고, 3번인덱스는 1개의 구간합 즉 그 값만 저장되고, 8번인덱스는 8개의 구간합이 저장된다.
그림으로 나타내면 아래와 같다.
홀수번은 최하위비트가 모두 첫자리의 1이므로 1개의 구간합을 가지며 짝수번은 각자 구간합을 가지게 되는 것
2번인덱스는 2개의 구간합을 가지므로 arr[1] + arr[2]의 구간합을 가지고
4번인덱스는 4개의 구간합을 가지므로 arr[1] + arr[2] + arr[3] + arr[4]의 구간합을 가진다.
이는 4번인덱스부터 앞으로 4칸의 구간합이다.
12번인덱스는 4개의 구간합을 가지고 12번부터 앞으로 4칸인 9~12번 구간의 합을 가진다.
특징으로는 2, 4, 8, 16같은 2의 거듭제곱수들은 1번인덱스부터 해당 인덱스까지의 누적합 값을 가진다.
또한 생성과 업데이트가 같은 코드로 구현된다.
정리하면
1) 펜윅트리는 비트를 이용해서 생성한다.
2) index를 2진수로 바꿔서 1이 존재하는 최하위비트의 값 x를 구한다.
3) 해당 index부터 x칸만큼 앞까지의 구간연산의 결과값을 갖는다.
이제 펜윅트리를 만들어보자
arr[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };이라는 배열이 있다.
먼저 펜윅트리로 쓰게 될 0으로 다 초기화된 16칸의 배열을 만든다.
그 다음 arr[1]의 값을 펜윅트리에 넣는다.
이 때 다른 인덱스들은 구간합을 저장하는 곳이므로 arr[1]이 포함되는 구간들은 모두 arr[1]만큼 더해줘야 한다.
위처럼 1번인덱스에 값을 넣으면 1번구간이 포함되는 모든 인덱스들에도 값의 변동이 필요하다.
값의 변동이 필요한 구간은 위에서 보이는 바와 같이 1, 2, 4, 8, 16인데
해당 구간을 찾는 방법은 아래와 같다.
1 = 0001
2 = 0010
4 = 0100
8 = 1000
16 = 10000
인데 찾는 방법은 1이 있는 최하위 비트를 찾아서 해당 위치에 1을 더해주는 방법이다.
즉 0001에서는 최하위비트 1이 가장 아랫자리에 있고 그 자리에 1을 더하면 0010이 된다.
0010에는 최하위비트 1이 밑에서 두번째자리에 있고 그 자리에 1을 더하면 0100이 된다.
이런식으로 펜윅트리의 범위를 벗어나기 전까지 1을 더해주면서 값을 ++해준다.
위 방법을 공식으로 표현하면 아래와 같다.
index번호 = index번호 + (index번호 & -index번호)위 공식을 사용하는 예시로는
9 = 1001이며
-9는 1001의 2의 보수이므로 1의 보수를 취한 뒤 1을 더해주면 된다.
즉 0110에 1을 더한 0111이 되고 1001 & 0111 이므로 0001이 된다.
즉 원래 값인 9의 1이 존재하는 최하위비트를 의미하며 해당 값을 더해주면 최하위비트에 1을 더한게 되는 것
void Update(int Idx, int diff)
{
while (Idx < Fenwick_Tree.size()) {
Fenwick_Tree[Idx] = Fenwick_Tree[Idx] + diff;
Idx = Idx + (Idx & -Idx);
}
}위 코드를 이용해서 펜윅트리를 생성할수도 있고, 배열의 값이 변경되는 경우 update용으로도 사용할 수 있다.
펜윅트리의 생성은 아래와 같다.
void Make_FenwickTree()
{
for (int i = 1; i <= N; i++) {
Update(i, arr[i]);
}
}
펜윅트리로 구간합 구하는 법 |
배열의 index 1 ~ 7의 구간합을 구하라고 한다면 아래의 노드들의 합을 계산해줘야 한다.
인덱스를 역순으로 작아지는 방법을 사용해야 하는데
7 = 0111
6 = 0110
4 = 0100
이며 작아지는 방법은 1이 존재하는 최하위비트를 찾아서 해당 비트에 1을 빼주면 된다.
그렇게 반복해서 0000이 나오면 종료한다.
위 방법을 공식으로 표현하면 아래와 같다
해당 index까지의 누적합 = 현재 index번호 - (현재 index번호 & -현재 index번호)
int Sum(int Idx)
{
int Result = 0;
while (Idx > 0) {
Result = Result + Fenwick_Tree[Idx];
Idx = Idx - (Idx & -Idx);
}
return Result;
}
펜윅트리와 세그먼트트리 |
펜윅트리는 세그먼트트리를 발전시킨 방법이지만 그렇다고 세그먼트트리보다 무조건 상위호환인건 아니다.
펜윅트리로 구현할 수 있는 모든 문제는 세그먼트트리로도 구현할 수 있다.
하지만 세그먼트트리로 구현하는 모든 문제를 펜윅트리로 구현하기에는 부적절할 수도 있다.
연산과 update만 있다면 펜윅트리와 세그먼트트리 모두 괜찮다.
하지만 구간에 대한 연산결과가 아니라 특정한 값을 찾는다면 ex) 최대값 최소값
펜윅트리는 누적의 개념을 사용하므로 구현이 더 복잡해진다.
그러므로 둘 다 정확히 알고 사용해야 한다고 한다.
최종적으로 코드 정리 |
#include <iostream>
#include <vector>
// 0번인덱스는 사용하지 않기위해 0 한개 붙여줌
// 원래의 배열은 1부터 16
std::vector<int> arr{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
std::vector<int> Fenwick_Tree(17, 0);
int N = 16;
void Update(int Idx, int diff)
{
while (Idx < Fenwick_Tree.size()) {
Fenwick_Tree[Idx] = Fenwick_Tree[Idx] + diff;
Idx = Idx + (Idx & -Idx);
}
}
void Make_FenwickTree()
{
for (int i = 1; i <= N; i++) {
Update(i, arr[i]);
}
}
int Sum(int Idx)
{
int Result = 0;
while (Idx > 0) {
Result = Result + Fenwick_Tree[Idx];
Idx = Idx - (Idx & -Idx);
}
return Result;
}
int main()
{
Make_FenwickTree();
std::cout << Sum(3) << '\n'; // 6출력
int Index = 1;
int Value = 5;
int Diff = Value - arr[Index];
Update(Index, Diff);
std::cout << Sum(3) << '\n'; // 10출력
return 0;
}
※ 참고 문헌