구간 트리(Segment tree) 비재귀 코딩방법

서론

우리는 많은 쿼리 문제를 만나게 된다. 특히, 그 중에서도 구간을 처리하는 쿼리문제는 많이 나오면서도 중요한데, 이를 일반적으로 naive하게 처리하면 망한다(...)

예를 들어, 구간의 최소값을 구하는 문제가 있다고 하자. 이 경우, 일반적으로 짜면 모든 구간을 다 돌면서 확인하는 식일건데, 쿼리의 개수를 Q라고 하고, 구간의 최대 길이를 N이라고 하면 O(QN)의 시간이 소요된다. 하지만, Q가 10만, N도 10만으로 주어지는 일반적인 문제에서는 TLE로 코드가 터지고 내 멘탈도 터지고(...)

어찌됐든, 다른 방안을 모색해야한다. 이 때 사용하는 것이 세그먼트 트리이다. 우리는 세그먼트 트리에 대해 자세히 알아보고, 일반적인 재귀로 짜는 방식 말고 비재귀로 짜는 방식에 대해 알아보겠다. ( 개인적으로 비재귀가 넘나 편함 )

본론

본격적으로 구간 트리에 대해 알아보자. 구간 트리는, 각 노드가 어떤 구간의 값을 담고 있는 것을 의미한다. 사진을 빌려서 표현하자면 이런식이다

(출처 : http://redsalmon.tistory.com/3 )

2-1 ) Build

문제에서 원하는 부분이 최대값이라고 가정하자. 그러면, 최상위 노드에서는 1~8까지의 최대값을, 그 다음 노드에서는 1~4와 5~8까지... 이렇게 가서 원소 하나를 가르칠 때 까지 트리를 구성한다.

여기서, 중요한것은 구간 트리는 이진 트리라는 것이다. Binary Tree여서, i의 원소에서 퍼져나갈 때에는 2*i와 2*i+1로 퍼져나간다. 

2-2) Update

update같은 경우엔, 업데이트 하는 값의 인덱스의 나누기 2한 인덱스를 갱신해주면 된다. i의 원소를 갱신하면, i/2도, i/4도... 이렇게 갱신해줘야함을 의미한다.

2-3) Answer

이렇게 트리를 구성하면, 값을 구하는건 어떻게 하는 것일까? 만약 우리가 4~8까지의 값을 구하고 싶다고 하자.

일단, 1~8에서 시작한다.

1~8을 기준으로, 4~8은 안에 포함되어 있는 구간으로 1~8의 최대값이 4~8의 최대값이란 보장이 없다. 따라서, 밑으로 내려간다.

1~4를 보자. 1~4는 4~8을 부분적으로 포함하고 있다. 이 경우, 값을 정확하게 할 수 없으므로 밑으로 내려간다.

다음은 1~2이다. 1~2랑 4~8은 전혀 다른 독립적 구간이라고 할 수 있다. 따라서, 무시하면 된다.

3~4 같은 경우에는 부분적으로 포함하고 있기 때문에 밑으로 내려간다.

3은 4~8과 독립적이기 때문에 무시하고, 4는 4~8 에 속하는 원소이므로 4를 반환한다.

이제 5~8 부분을 보자

4~8과 5~8은 포함 관계이다. 그것도, 4~8이 5~8을 포함한다. 이 경우에는, 그냥 5~8까지의 최소값을 반환한다.

이렇게 반환한 두 값중에서, 최소값을 골라주면 우리가 원하는 값이 된다.

본론-2) 구현

2-1) Build()

void build()
{
    for(int i=N-1; i >= 1; i--)
        t[i] = t[i << 1] + t[i << 1 | 1];
}

n<<1 = n*2, n|1 = n+1( n이 짝수 ), n( n이 홀수 )

앞에서 말했다시피, i번째 원소는 2*i과 2*i+1의 구간을 종합하여 만들어진다.

void update(int pos, int val)
{
    for(t[pos += N] = val; pos > 1; pos >>= 1)
        t[pos >> 1] = t[pos] + t[pos ^ 1];
}

n>>1 = n/2, n^1 = n+1( n이 짝수 ), n-1( n이 홀수 )

앞에서 말했다시피, i번째 원소가 갱신되면, i/2도 갱신해줘야 한다.

2-3) Answer()

ll sum(int l, int r)
{
    ll ans = 0;
    for(l += N, r += N; l < r; l >>= 1, r >>= 1)
    {
        if(l & 1)
            ans += t[l++];
        if(r & 1)
            ans += t[--r];
    }
    return ans;
}

여기서 구간은 [l,r)이다.

l,r 구간에서 l이 들어가면 l+1도 들어간다.

그리고, build할 때 구간을 정할때 사용되는 두 값은 2*i와 2*i+1이다.

따라서, l이 짝수일 경우엔 l과 l+1 모두 구간에 들어가기 떄문에 위쪽으로 올라가주면 된다.

하지만, l이 홀수일 경우엔 l-1은 구간에 안들어가기 떄문에, 현재 l값을 바탕으로 답을 갱신해줘야 한다.

l이 홀수인지 조사하는 코드는 l&1이다

반대로, r이 홀수면 r과 r-1 모두 구간에 들어가기 떄문에 위쪽으로 올라가주면 된다.

하지만, r이 짝수면 r+1은 구간에 안들어가기 때문에, 현재 r값을 바탕으로 답을 갱신해줘야한다.

구간이 [l,r)이므로, r이 홀수가 되면 r을 하나 까고 그 깐 r을 갱신해준다.

ll은 long long 자료형의 줄임이고, 이는 icpc.me/2042를 기반으로 해서 짠 코드이다.

Build()할 때에는 총 2*N-1개의 원소를 갱신하므로 O(2N) = O(N)이 걸린다.

update() 할 떄에는, log N 번만큼 갱신이 필요하므로 O(log N)이 된다.

답을 구하는 과정도, l이 1이고 r이 N이라고 생각하면, 총 log N번 계산하므로 O(log N)이다.

따라서, 전처리는 O(N), 각 쿼리당 O(log N)해서 총 시간복잡도는

O(QlogN + N)이 된다.

결론

사람들은 누구보다 비재귀를 좋아하면서 왜 싫어하는척 할까?

비재귀가 한번 손에 익으면 벗어날 수 없다...

lazy propagation도 간단하다는 썰이 있다.

이는 아직 공부를 안해서.. 공부를 하고 포스팅을 하도록 하겠다

들리는 소문으로는 비재귀는 gcd 트리를 갱신못시킨다카더라..