지난 게시글에서 세그먼트 트리에 대해 알아보았다.
펜윅트리는 세그먼트 트리에서 조금 더 진보된 형태라고 보면 된다.
비트연산을 이용하기 때문에, 처음에 이해하는 것이 다소 까다롭지만 완벽히 이해하고 나면
구현하는 것도 훨씬 간단하고 메모리 사용량도 상대적으로 적기때문에 세그먼트 트리보다 효율적인 알고리즘이다.
위는 세그먼트 트리의 구조이다.
N개의 숫자에 대해 저장하는 구간합의 최대 개수는 약 4N개이다.
반면, 아래 그림은 펜윅 트리이다.
위 그림은 펜윅트리에서 각 인덱스에 저장된 구간합의 정보이다.
어떤 기준으로 합이 저장되고, 어떻게 사용하는지는 일단 뒤로 미루고 전체적인 크기를 보자.
세그먼트 트리는 구간합에 대한 정보를 트리구조로 저장하기 때문에 최대 4N개의 메모리가 필요했다.
반면, 펜윅트리는 숫자N개에 대한 N개의 배열 하나에 구간합의 정보를 모두 저장하고 있다.
메모리를 1/4로 절약할 수 있는 것이다.
메모리를 아끼는 만큼 구간합을 구할 때, 시간복잡도가 더 크지 않을까? 라는 생각을 할 수도 있지만
시간복잡도는 O(logN)으로 동일하다.
또한 펜윅트리는 비트연산을 이용하기 때문에, 같은 시간복잡도여도 재귀함수를 사용하는 세그먼트 트리보다 더 빠르다.
즉, 가능하다면 펜윅트리를 사용하는 것이 훨씬 효율적이라는 것이다.
다만, 펜윅트리를 모든 상황에서 사용할 수 있는 것은 아니다.
세그먼트 트리 게시글에서 구간 합에 대해서만 언급하였지만, 실제로는 구간의 최소값, 최대값 등을 구하기 위해서도 세그먼트 트리를 활용할 수 있다.
반면 펜윅트리는 구간의 합과 같은 몇가지 정보에 대해서만 사용이 가능하다. 기능이 다소 제한적이라는 뜻이다.
이유는 뒤에서 설명하겠지만, 펜윅트리는 합을 구하는 연산을 할 때, 1~K로만 구할 수 있다.
세그먼트 트리는 a~b구간에 대해, 그 사이에 있는 여러 구간을 활용하여 a~b의 구간합을 구하지만,
펜윅트리는 1~b 의 구간합에서 1~(a-1)의 구간합을 빼는 방식으로 이루어진다.
즉, 펜윅 트리에서 직접적으로 구할 수 있는 것은 구간합이 아니라 누적합인 것이다.
이러한 이유로 펜윅 트리는 다소 사용할 수 있는 상황이 제한적이기 때문에, 상황에 맞게 잘 사용해야 한다.
이제 펜윅트리가 어떻게 작동하는지 확인해보자.
펜윅 트리
펜윅 트리에도 세그먼트 트리와 동일하게 Update와 GetSum함수 두가지가 있다.
세그먼트 트리는 초기화 함수도 따로 있었지만, 세그먼트 트리는 Update를 활용해서 초기화를 진행할 수 있기 때문에 초기화 함수가 따로 필요하지는 않다.
먼저 이 그림을 보자.
1의 경우 1로부터 앞쪽으로 1칸의 구간합을 저장하고 있다.
2의 경우 2로부터 앞쪽으로 2칸의 구간합을 저장하고 있다.
3의 경우 3으로부터 앞쪽으로 1칸의 구간합을 저장하고 있다.
4의 경우 4로부터 앞쪽으로 4칸의 구간합을 저장하고 있다.
쭉쭉 해보면 8의 경우엔 8로부터 앞쪽으로 8칸의 구간합을 저장하고 있다.
정확한 규칙성은 모른다 하더라도, 일단 2의 지수에 해당하는 칸의 구간합을 저장하고 있다는 것은 쉽게 알 수 있다.
규칙성을 찾기 위해 이진수의 형태로 인덱스를 확인해보자.
1-> 1
2-> 10
3-> 11
4-> 100
5->101
6->110
7->111
8->1000
여기서 최하위 비트에 집중을 해보자.
최하위 비트란, 이진수에서 가장 오른쪽에 있는 1을 의미한다.
위의 표는 각 인덱스를 이진수로 표현했을 때, 최하위 비트가 오른쪽으로 부터 몇 번째에 있는가를 기록한 표이다.
해당 배열의 원소값을 n이라고 했을 때, 2^(n - 1)을 구해보자.
이렇게 값이 변하게 된다.
보면 어디서 본 것 같은 숫자가 나온다.
위에서 구해보았던 구간합의 개수 정보이다.
4번 인덱스의 경우 원소값이 4가 되는데, 이 경우 4로부터 앞으로 4칸에 대한 구간합을 저장하겠다는 것이다.
8의 경우, 8로부터 앞으로 8칸까지의 구간합을 저장하겠다는 것이다.
일단, 이 정보만을 기억해두고 Update과정에 대해 알아보자.
만약, 3번째 숫자를 변경하고 싶다면, 위의 그림에서 주황색으로 표현된 곳처럼 3번 숫자를 포함하고 있는 구간합의 정보를 갱신해야 한다.
즉, 3번 숫자가 바뀌게 되면 펜윅트리에선 3, 4, 8 번의 구간합을 수정해야 하는 것이다.
3, 4, 8을 이진수로 표현해보자.
3-> 11
4-> 100
8->1000
3의 최하위 비트는 1이다.
3에다가 이진수 1을 더해보자.
100이 된다. 11 + 1 -> (3 + 1) -> 4 -> 100
이번엔, 4를 보자.
4의 최하위 비트는 3번째 1이고, 이진수로는 100이다.
4에다가 이진수 100을 더해보자.
1000이 된다. (100 + 100) -> 4 + 4 -> 8 -> 1000
즉, 변경된 숫자의 인덱스에서 최하위 비트를 더해가며 나오는 값이 변경된 숫자가 포함된 구간의 인덱스가 되는 것이다.
반복문을 돌며, 최하위 비트를 더해가며 인덱스를 구하면서 구간합을 갱신하면 끝이다.
다음은, 구간합을 구하는 법에 대해 알아보자.
위에서도 말했듯이 정확히는 누적합이다.
펜윅트리에서 직접적으로 구할 수 있는 구간은 무조건 1부터 시작한다.
K까지의 구간합을 구하게 되면 1~K의 합을 반환하기 때문에 누적합이라고 표현하는 것이 조금 더 적합하다.
N~K 의 구간합을 구하고 싶다면, [1 ~ K] - [1 ~ (N - 1)] 의 방식으로 구간합을 구하게 된다.
구간합을 구하는 방식은 업데이트와 반대이다.
이번엔 최하위 비트를 빼면서 계산하면 된다.
예를 들어, 7까지의 누적합을 구한다고 해보자.
이진수로 표현하면 7은 111이다.
최하위 비트는 첫번째 1이고, 이진수로는 1이다.
111에서 1을 빼면, 110이 된다.
110은 십진수로 6이다.
이번엔 6에서 다시 최하위 비트를 빼보자.
110의 최하위 비트는 2번째 1이고, 이진수로는 10이다.
110 에서 10을 빼면, 100 -> 4가 나온다.
다음은 4에서 다시 최하위 비트를 빼보자.
100의 최하위 비트는 세번째 1이고, 이진수로는 100이기 때문에
4에서 최하위 비트를 빼면 0이 나온다.
즉, 이제 더이상 더할 것이 없다는 것이다.
이 결과대로라면 펜윅트리의 7번 인덱스 + 6번 인덱스 + 4번 인덱스의 값이 1~7의 누적합이 되는 것이다.
그림에서 보면, 7번 인덱스 + 6번 인덱스 + 4번 인덱스의 값이 [1] ~ [7]까지의 합인 것을 확인할 수 있다.
이처럼, 펜윅트리는 최하위 비트를 활용하여 트리를 갱신하고 누적합을 구하게 된다.
개념 자체는 다소 복잡하지만 코드로 구현해보면 매우 간단하다는 것을 알 수 있다.
이제, Update와 GetSum을 알아보았으니 초기화 과정도 알아보자.
위에서 말했듯이 초기화는 Update를 이용해서 구현한다고 하였다.
최초에 배열은 이렇게 비어있다.
모든 값이 현재 0으로 저장되어 있는 것이다.
숫자가 위와 같이 주어진다면, 이 것을 변경되는 값이라고 가정하고 Update를 진행하는 것이다.
1번 인덱스의 숫자가 현재 1이다. 이를 숫자가 0->1로 변경되었다고 가정해보자.
그렇다면, 1번 숫자가 포함된 구간합을 저장하고 있는 펜윅트리의 인덱스를 모두 갱신해야 한다.
위에서 설명했던 최하위 비트를 활용하여 갱신하게 되면 아래와 같아진다.
2번 숫자에 대해서도 갱신해보자.
3번 숫자에 대해서도 갱신하면?
이런 식으로 펜윅 트리가 계속 갱신된다.
즉, 맨 처음의 숫자가 모두 0이었다가 주어진 숫자로 변경되었다고 가정하고 모든 숫자에 대해 Update를 진행하게 되면
규칙대로 구간합을 저장하게 되는 것이다.
최종적으로는 이렇게 펜윅 트리가 완성된다.
이제 코드로 구현해보자.
코드 구현
std::vector<int> Nums;
std::vector<int> FenWickTree;
먼저 숫자를 저장할 벡터와 구간합을 저장할 펜윅트리 두 가지를 선언해주었다.
Nums.resize(NumSize + 1);
FenWickTree.resize(NumSize + 1);
이후, resize를 해주었다. 세그먼트 트리와 동일하게 펜윅트리도 인덱스 0번을 사용하지 않고 1번부터 사용한다.
왜냐하면 0의 이진수는 0이기 때문에 최하위 비트를 활용한 연산이 불가능하기 때문이다.
void Update(int _Index, int _Value)
{
while (_Index < Nums.size())
{
FenWickTree[_Index] += _Value;
_Index += (_Index & -_Index);
}
}
그리고, 초기화를 하기 위해 Update함수를 먼저 정의하였다.
_Index는 변경된 숫자의 인덱스이고, _Value는 변화량이다.
1->3으로 바뀌었다면 _Value는 3이 아니라 2이다.
5->2로 바뀌었다면 _Value는 2가 아니라 3이다.
반복문 내부를 보면 &연산자를 이용해 비트연산을 진행하고 있다.
비트 연산에 익숙하지 않은 사람은 해당 연산이 뭘하는건지 잘 모를 수 있다.
먼저, 숫자 15를 비트로 표현해보자.
int자료형이라면 실제로는 32자리가 되겠지만, 편의를 위해 8자리만 사용해 설명하도록 하겠다.
15를 비트로 표현하면, 0000 1111이 된다.
-15는 어떻게 표현할까?
결론부터 말하자면, -15는 1111 0001이다.
어떤 비트의 부호를 바꾸고 싶다면, 1와 0을 모두 뒤집은 뒤 1을 더해주면 된다.
0000 1111 의 0과 1을 모두 뒤집게 되면 1111 0000 이 된다.
여기서 1을 더해주면? 1111 0001 이 된다.
여기서, -15와 15는 2의 보수라고 표현하기도 한다.
왜냐하면 1111 0001과 0000 1111을 수학적으로 더하면, 1 0000 0000 이 된다. 절대값은 같지만 부호가 다른 두 수를 더하면 최대 비트를 초과하면서 가장 작은 2의 제곱수가 나오게 되는데, 수학에서 이 것을 2의 보수라고 한다.
하지만, 컴퓨터 공학에선 1111 0001 과 0000 1111을 더한다고 1 0000 0000 이 나오지는 않는다.
1111 0001은 -15이고, 0000 1111은 15이다. 두 수를 더하면 0이 나온다.
0의 비트는 0000 0000 이다.
즉, 1111 0001 과 0000 1111을 더하면 0000 0000이 나온다는 뜻인데, 이는 컴퓨터 공학에서 비트 연산이 수학적인 이진수 덧셈과는 다르다는 것을 알려주는 부분이다.
그럼에도 2의 보수라는 단어를 사용하는 이유는 그냥 수학에서 2의 보수라고 하니까 관습적으로 사용하는 것 같다.
15의 비트 -> 0000 1111
-15의 비트 -> 1111 1001
두 비트의 &연산을 하게 되면 두 비트 모두 1인 비트는 1로, 다른 비트는 0으로 표현하여 반환하게 된다.
즉 15 & -15 를 하게 되면 0000 0001 이라는 비트가 반환된다.
최하위 비트를 구할 수 있는 것이다.
한 번 더 확인하기 위해 이번엔 19와 -19를 &연산 해보자.
20의 비트 -> 0001 0100
-20의 비트 -> 1110 1100
20 & -20 -> 0000 0100
이 번에도 최하위 비트를 반환하였다.
이 결과를 보면 Num과 -Num을 &연산한 결과는 Num의 최하위 비트라는 것을 알 수 있다.
이를 이용해, 인덱스에 최하위 비트를 더해주면서 최대 인덱스를 초과하기 전까지 펜윅 트리를 갱신하는 것이 Update 함수이다.
다음은 누적합을 구하는 GetSumFromZero 함수이다.
본인은 GetSumFromZero와 GetSegSum함수를 분리해놓았는데
GetSumFromZero는 누적합을 구하는 함수이고, GetSegSum함수는 원하는 구간의 구간합을 구하는 함수로 만들었다.
int GetSegSum(int _Start, int _End)
{
return GetSumFromZero(_End) - GetSumFromZero(_Start - 1);
}
구간합은 위에서 설명했듯이, 두 누적합의 차를 반환하면 된다.
int GetSumFromZero(int _Index)
{
int Sum = 0;
while (_Index > 0)
{
Sum += FenWickTree[_Index];
_Index &= (_Index - 1);
}
return Sum;
}
누적합을 구하는 함수는 위와 같다.
누적합을 구할 때에는 최하위 비트를 빼면서 값을 더한다고 하였다.
그런데, while문 내부를 보면 위에서 보았던 양수와 음수의 &연산을 통해 최하위 비트를 구하고 있지 않다.
물론 위에서 설명한 방식으로 해도 된다. 다만, 한 가지 방식이 더 있기 때문에 보여주기 위해 사용하였다.
먼저, 최하위 비트를 뺀다는 것은 다른 비트는 그대로 냅두고 최하위 비트만 0으로 만들겠다는 것이다.
1110 0101 이라면 1110 0100으로 만들고, 0000 1000이라면 0000 0000으로 만드는 것이다.
Index를 7이라고 가정해보자. 7은 0000 0111이 된다.
여기서 1을 빼면, 0000 0110이 된다.
두 수를 &연산하면, 0000 0110이 나온다. 최하위 비트를 뺀 값이 나왔다.
이번엔, Index를 20이라고 가정해보자.
20은 0001 0100이 된다.
여기서 1을 빼면, 0001 0011이 된다.
두 수를 &연산하면 0001 0000이 된다.
결과를 보면 _Index 와 _Index - 1 을 &연산하면, _Index에서 최하위 비트를 뺀 값이 나온다는 것을 알 수 있다.
비트의 마지막 수가 1이라면, 1을 뺐을 때 마지막 수가 0이된다.
측, 최하위 비트가 1에서 0으로 바뀌는 것이다.
그러므로 기존의 값과 &연산을 하게 되면 마지막 값만 0으로 바뀐 채로 나머지 비트는 유지된다.
반면, 비트의 마지막 수가 0이라면, 1을 뺐을 때 최하위 비트의 값이 1->0으로 바뀐다.
0100에서 1을 빼보자. 0011이 된다.
0010에서 1을 빼면, 0001이 된다.
1000에서 1을 빼면, 0111이 된다.
1011 0100에서 1을 빼면, 1011 0011이 된다.
즉 1을 빼면, 가장 오른쪽 비트부터 최하위 비트까지 0과 1이 반전된다.
그러므로, Num 과 Num - 1을 &연산하면 최하위 비트는 서로 다르기에 0이 되고, 나머지 값은 모두 그대로 보전이 된다.
(최하위 비트 뒤의 값은 서로 달라 &연산을 하면 0이 되지만, 최하위 비트의 특성을 생각해보면 원래 0이었기 때문에 값에 변함이 없다. 최하위 비트 앞의 값들은 변하지 않았기 때문에 &연산을 하여도 값이 변하지 않는다.)
코드를 모두 정리하면 아래와 같다.
std::vector<int> Nums;
std::vector<int> FenWickTree;
int GetSumFromZero(int _Index)
{
int Sum = 0;
while (_Index > 0)
{
Sum += FenWickTree[_Index];
_Index &= (_Index - 1);
}
return Sum;
}
int GetSegSum(int _Start, int _End)
{
return GetSumFromZero(_End) - GetSumFromZero(_Start - 1);
}
void Update(int _Index, int _Value)
{
while (_Index < Nums.size())
{
FenWickTree[_Index] += _Value;
_Index += (_Index & -_Index);
}
}
int main()
{
//숫자는 모두 입력받았다고 가정하자.
Nums.resize(NumSize + 1);
FenWickTree.resize(NumSize + 1);
//초기화
for (int i = 1; i <= NumSize; i++)
{
Update(i, Nums[i]);
}
}
위와 같은 값에 대해 테스트 해보자.
먼저 초기화 함수를 테스트해보자.
초기화가 잘 된 것을 확인할 수 있다.
다음은 GetSegSum함수를 테스트해보자.
매우 잘 구해지는 것을 확인할 수 있다.
'C++ > 알고리즘' 카테고리의 다른 글
| 알고리즘 - 단조 스택 (Monotonic Stack) (1) | 2024.04.26 |
|---|---|
| 알고리즘 - 라인 스위핑 (0) | 2024.04.21 |
| 알고리즘 - 세그먼트 트리 (구간의 합 구하기) (0) | 2024.04.12 |
| 알고리즘 - 에라토스테네스의 체 (소수 판별) (0) | 2024.04.09 |
| 알고리즘 - 유니온 파인드 (노드의 집합 판별하기) (0) | 2024.04.09 |