PS. FenwickTree 그전에 SegmentTree

오랜만에 세그먼트 트리 문제를 풀게 되었는데, 예전에 한창 풀다가 오랜만에 풀라고 하니까 기억이 안 나서 다시 정리를 하려고 한다. 보통 세그먼트 트리 문제들은 펜윅트리. 그래서 나도 펜윅트리를 알고 나서는 세그 트리 문제들 펜윅트리로 많이 풀었다. 근데 또 특정 값을 구하거나 그런 문제들에는 안되서 좀 변형하면 되긴한다. 근데 펜윅트리 같진 않다. 아무튼 펜윅트리를 알기 전에 당연히 세그 트리를 알면 좋고 세그 트리는 응용해서 다 풀 수 있다. 그래서 간단하게 세그먼트 트리 특징 정리하고 코드 보고 펜윅트리 비교하고 끝내겠다. 먼저 예제로는 백준 2042번 구간 합 구하기라는 문제를 풀 거다. 간단하게 정리하겠지만 전체 개념은 밑에 블로그를 참고하면 될 거 같다. 정말 디테일하게 정리해주셨다. 

https://yabmoons.tistory.com/431

[ 세그먼트 트리(Segment Tree) ] 개념과 구현방법 (C++)

세그먼트 트리르 간단하게 정리하면 크게 2가지 연산을 한다고 한다. 첫 번째는 a~b까지의 구간합을 구하여라. 두 번째는  a번째 값을 b로 바꾸세요 같은 업데이트 연산이다. 이러한 연산이 M번 주어진다고 하면 첫 번째 연산은 O(N)만큼 시간이 소요되고 두 번째 연산은 O(1) 만큼 소요된다고 한다. 근데 세그먼트 트리를 사용하면 O(logN)만큼 걸린다고 한다. 세그먼트 트리를 만들 때 높이를 통해서 크기를 결정하는데, 자세한 형태와 이유는 위의 블로그 참고하자. 아무튼 높이는 ceil(log2(N)) 이런식으로 구하고 세그먼트 트리의 크기는 (1 << (트리의 높이 + 1) ) 이런 식으로 구한다. 구현할 때 편하게 원래 크기*4 이런 식으로 해줘도 공간이 충분하다. 그리고 이러한 공간에서 이점을 가져가는 게 펜윅트리인데이따가 설명 하겠다.

다음으로 세그먼트 트리를 구체적으로 어떻게 구현하는지 살펴보자. 일단 재귀를 통해서 구현하는데, 트리의 형태로 구간을 계속 나누다가 같은 구간일 때 값을 설정해준다. 보통 맨 처음 트리를 생성하는 코드를 만들고 위에서 언급한 구간합 구하는 함수, 업데이트 함수를 만든다. 문제마다 좀 다르긴 한데, 생성 함수가 필요 없이 업데이트 함수와 질의 함수만을 만들어 해결하는 문제도 많다. 2042 코드를 예시로 살펴보자

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long

int N,M,K;
ll tree[3000000];
ll num[1000001];

void update(int n, int s, int e, ll t, ll diff)
{
   if (s <= t && t <= e)
        tree[n] += diff;
    else
        return;
    if (s == e)
        return;
    int m = (s + e) / 2;
    update(n * 2, s, m, t, diff);
    update(n * 2 + 1, m + 1, e, t, diff);
}
ll sum(int l, int r, int n, int s, int e)
{
    if(r<s || l>e) return 0;
    if(l<=s && e<=r) return tree[n];
    
    int mid =(s+e)/2;
    return sum(l,r, n*2 ,s, mid)+ sum(l,r ,n*2+1 ,mid+1, e);
    
}
ll init(int n, int s, int e)
{
   if(s==e) return tree[n] = num[s];
   int mid = (s+e)/2;
   tree[n] = init(n*2, s,mid) + init(n*2+1, mid+1,e);
   return tree[n];
}
int main()
{
    cin>>N>>M>>K;
    for (int i = 1; i <= N; ++i){
    	cin>>num[i];
	}
       
    init(1, 1, N);

    for (int i = 0; i < M + K; ++i)
    {
        ll a, b, c;
       cin>>a>>b>>c;
        if (a == 1)
        {
             ll diff = c - num[b];
            num[b] = c;
            update(1, 1, N, b, diff);
        }
        else
            cout<<sum(b, c, 1, 1, N)<<endl;
    }
}

재귀를 통해 구현이 되었고 먼저 구간합 부분을 보자면 3가지 경우로 나뉘는데 첫 번째는 전혀 구간이 맞지 않은 경우 두 번째는 현재 구간이 내가 구하려고 하는 범위 안에 있는 경우, 마지막은 일부만 걸친 경우다. 다음으로 업데이트는 위에서 말한 거처럼 init과 굉장히 비슷한데, target값이 속하는 구간들은 모두 값을 업데이트 시켜줘야 한다. 자세한 경우는 블로그를 참고하자. 그럼 일단 바로 비교를 위해 펜윅트리 예제 부터 보자.

#include<bits/stdc++.h>
 
#define endl "\n"
#define ll long long

using namespace std;

vector<ll> tree;
vector<ll> v;

ll sum(ll idx){
	ll res =0;
	while( idx){
		res+= tree[idx];
		idx -= (idx &-idx);
	}
	return res;
} 

void update(ll idx ,ll val){
	while(idx<tree.size()){
		tree[idx] +=val;
		idx += (idx&-idx);
	}
}

int main(){
	
	fastio; 
	
	int n,m,k;cin>>n>>m>>k;
	v.resize(n+1,0);
	tree.resize(n+1,0);
	for(int i=1; i<=n ;i++){
		cin>>v[i];
	}
    
	for(int i=1; i<=n; i++){
		update(i,v[i]);
	}

	for(int i=0; i<m+k; i++){
		ll cmd	,a,b;
		cin>>cmd>>a>>b;
		if(cmd==1){
			ll diff=b-v[a];		
			v[a]=b;
			update(a,diff);
		}
		else{
			cout<<sum(b) - sum(a-1) <<endl;
		}
	}
	
	return 0;	
}

한눈에 봐도 코드가 간단해 보인다. 위에서 말한거 처럼 펜윅트리는 메모리도 덜 쓸 수 있고 구현이 훨씬 간단하다. 그리고 차이점이라면 누적합 개념을 사용한다.

펜윅트리의 구현 과정을 간단하게 정리해보자. 먼저 간단한 비트 연산을 알아야 하는데, 그전에 밑에 참고한 블로그에 가서 그림을 머릿속에 넣고 설명을 쭉 보자. 이 그림을 머리에 넣어놓으면 훨씬 편하다. 간단하게 정리해 보면 최하위 비트 값을 가지고 연산을 진행한다. 구간합을 구하려면 구하려는 인덱스에서 최하위 비트를 빼가면서 값들을 다 더해주면 된다. 또한 업데이트 연산을 하려면 기존 인덱스에서 최하위 비트에 1을 더하면서 값을 추가해 주면 된다. 블로그 그림을 계속 떠올리면 편하다. 문제 풀 때도 헷갈리면 그림 떠올리면 된다. 비트 연산에 대한 설명을 추가로 하자면 (idx &-idx) 이 부분이 최하위 비트 찾는 연산이다. 직접 해보면 바로 나온다 예를 들어 1010 이면 이거 음수가  0101에 +1 한 0110 이니까 이거랑 기존 꺼랑 & 연산해주면 0010이 나온다. 

 

사실 세그먼트 트리 문제를 예전에 백준에서 비슷한 유형이 많아서 많이 풀었던 기억이 있는데, 백준 문제를 전부 다 풀지는 않았지만, 유형을 어느 정도 정리해보면 inversion counting이라고 역순 돼있는 개수 찾는 문제들 꽤 있다. 막 연결하는데 엉킨거 갯수 찾는 거 등 비슷하다. 그리고 몇 번째 수 찾는 질의가 필요한 문제들도 꽤 있다. 익숙해지면 약간의 변형을 통해 풀 수 있는 거 같다. 오랜만에 세그먼트 트리를 보니까 쉽게 풀리지는 않는데 다시 자주 봐서 익숙하게 만들어야겠다.

 

 

참고 및 출처:

https://yabmoons.tistory.com/431

[ 세그먼트 트리(Segment Tree) ] 개념과 구현방법 (C++)

https://yabmoons.tistory.com/438