[ 개념 ] 41. 세그먼트 트리(Segment Tree)

> 세그먼트 트리(Segment Tree)

---

각 구간들을 그대로 보존하고 있는 트리

전체 구간이 [0, N-1]이라 할 때, 즉 N개의 공간이 있을 때

이렇게 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고

부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이어야만 합니다.

루트는 전체 구간을 포함하게 됩니다.

이렇게 각 노드가 구간, 혹은 그 구간의 정보를 저장하고 있는 자료구조를 말합니다.

보통은 완전 이진 트리의 형태를 사용해 전체적으로 동일한 재귀적 구조가 반복되도록 이렇게 표현하며, 값의 개수가 2^n 꼴이 아닐 때 남는 구간을 의미없는, 혹은 기본 값으로 채워서 포화 이진 트리 형태로 사용하는 게 대부분입니다.

이렇게 하면 값이 N개일 때 반드시 트리의 높이가 O(logN)으로 균형잡혀 있기 때문이죠!

그리고 힙 때와 마찬가지로 루트의 인덱스가 1부터 시작되며 레벨 오더 순번으로 노드 번호를 매겨서 자신의 부모, 왼쪽/오른쪽 자식을 접근하게 쉽게 합니다.

즉, [0, 7]은 1번, [0, 3]은 2번, [4, 7]은 3번, [0, 1]은 4번...

그리고 리프 노드들은 8, 9, 10, ... , 15번으로 N ~ 2N-1번의 번호를 얻게 됩니다. 번호는 곧 인덱스라고 생각해도 좋습니다.

BOJ[2042] : 구간합구하기

https://www.acmicpc.net/problem/2042

이 문제를 살펴봅시다. 값이 N개이고 쿼리가 2개의 형태로 들어옵니다.

하나는 b번째 값을 c로 바꾸라는 것이고 하나는 구간 [b, c]에 속한 모든 원소의 합을 구하란 거네요.

만약 두 번째 쿼리만 있었다면 구간 합 배열(https://kks227.blog.me/220787178657)만을 사용하여 문제를 풀 수 있었을 것인데, 문제는 도중에 값을 바꾸는 쿼리가 들어온다는 점...

이 때문에 값을 바꿀 때마다 구간 합 배열을 O(N)으로 갱신해줘야 해서 쿼리 개수를 Q(=M+K)라 하면 전체 O(NQ)의 시간복잡도를 피할 수 없게 됩니다. 즉 시간초과...

그래서 좀 더 최적화된 자료구조가 필요하게 되었습니다!! 그것이 세그먼트 트리입니다.

세그먼트 트리는 구간 정보로 사용자가 원하는 아무 값이나 저장해 두는데,

가장 대표적인 것이 구간에 속한 원소들의 합, 구간에 속한 원소들의 곱, 구간 원소들 중 최댓값, 구간 원소들 중 최솟값 등이 있습니다. 즉...

위의 문제를 풀기 위해 자신이 포함하는 구간의 원소의 합을 갖고 있으면 이렇게 됩니다.

여기서 만약 구간 전체의 합을 알고 싶다면 바로 루트를 보면 됩니다. 14네요.

구간 [0, 3]의 합은? 그에 해당하는 노드가 2번입니다. 그 값이 9네요.

구간 [4, 5]는? 6번 노드를 보면 됩니다. 그 값이 4네요.

구간 [6, 6]은? 이건 리프 노드인 14번 노드의 값이자 그냥 배열의 6번 원소인 0이 되겠습니다.

이렇게 구간에 딱 맞춰 대응하는 노드가 있으면 그 노드의 값으로 구간 합을 구할 수 있음은 쉽게 알 수 있습니다.

그런데 하나의 노드로 표현할 수 없는 구간은? 예를 들면 [0, 2]나 [3, 6]은 어떻게 할까요?

구간 [0, 2]의 합을 구하는 방법입니다.

보시면 구간을 여러 개로 쪼개서 트리상의 노드들로만 표현이 가능하게 해버렸죠.

[0, 1]과 [2, 2] 구간으로 쪼개서 그 각각의 합을 구했습니다.

구간 [3, 6]의 합을 구하는 방법입니다. 이번엔 저 빨간색 노드들의 합을 더하면 됩니다.

구간 [2, 7]의 합입니다.

지금까지 예시를 보면 모두 구간을 여러 개로 쪼개고, 동시에 그 쪼개서 생기는 구간의 개수도 최소화하고 있습니다.

즉 어떤 넓은 구간이 원래 합을 구하려는 구간에 포함된다면 그 구간은 더 쪼개지 않고 바로 자신에 대응하는 노드 값을 보태버리면 됩니다.

만약 구간 [0, 1]과 [2, 3]이 동시에 목표 구간에 포함된다면 그 둘을 합친 구간 [0, 3] 또한 해당하는 노드가 있으므로 [0, 3] 구간을 쪼개지 않고 그 노드 값으로 처리하겠다는 거죠.

이걸 재귀함수로 구현할 수 있습니다. 먼저 루트부터 내려가면서, 구하려는 구간에 이 노드가 완전히 포함되면 자신의 값을 리턴하고, 아니면 구간을 양쪽으로 쪼개서 각각 재귀호출해 두 함수의 결과를 더하면 됩니다.

만약 이 노드의 구간이 목표 구간과 전혀 겹치지 않으면 더 탐색할 필요없이 역시 종료해버리면 됩니다.

구간 [L, R]에서 목표 구간에 속하는 원소들의 합을 구하는 함수를 sum(L, R)이라 해봅시다.

세 번째 그림을 예로 들어보자면 우리가 목표로 하는 구간이 [2, 7]이고, 맨 처음엔 루트인 [0, 7]부터 시작합니다. 즉, sum(0, 7)을 불러서 시작합니다.

호출된 sum(0, 7)은 이런 행동을 합니다. [0, 7]이 [2, 7]에 포함되지는 않으므로 구간을 양분해 [0, 3], [4, 7]로 나누어서 각각을 재귀호출해 그 결과를 더하도록 합시다. 즉, sum(0, 3)과 sum(4, 7)을 부릅니다.

sum(0, 3)은 마찬가지로 sum(0, 1)과 sum(2, 3)을 부릅니다.

sum(0, 1)은 목표 구간 [2, 7]과 겹치는 구간이 전혀 없으므로 0을 리턴하며 종료합니다.

sum(2, 3)은 목표 구간 [2, 7]에 완전히 포함되므로 자신의 값 4를 리턴합니다.

sum(0, 3)은 따라서 0+4 = 4를 리턴합니다.

sum(4, 7) 또한 [2, 7]에 완전히 포함되므로 바로 5를 리턴합니다.

최종적으로 sum(0, 7) = sum(0, 3) + sum(4, 7) = 4 + 5 = 9가 됩니다.

대충 이런 식으로 재귀호출이 이루어집니다.

 int sum(int L, int R, int nodeNum, int nodeL, int nodeR){
        if(R < nodeL || nodeR < L) return 0;
        if(L <= nodeL && nodeR <= R) return arr[nodeNum];
        int mid = (nodeL + nodeR) / 2;
        return sum(L, R, nodeNum*2, nodeL, mid) + sum(L, R, nodeNum*2+1, mid+1, nodeR);
 }

매개변수가 좀 많은데 종만북의 코드를 거의 그대로 옮긴 겁니다.

nodeNum은 현재 보고 있는 노드의 번호(인덱스)이고 nodeL과 nodeR은 그 노드가 포함하는 구간을 의미합니다. L과 R이 본래 우리가 구하고자 하는 구간이고요.

따라서 구간 [L, R]의 합을 구하고 싶을 때는 맨 처음에 sum(L, R, 1, 0, N-1)을 호출해야 합니다. N이 값의 개수, 즉 전체 구간의 크기입니다. 루트 번호는 1이구요.

첫 번째 줄은 [nodeL, nodeR]과 [L, R]이 전혀 안 겹치는 경우. 바로 0을 리턴하는데 0은 덧셈에 영향을 미치지 않죠.

두 번째 줄은 [nodeL, nodeR]이 [L, R]에 완전히 포함되는 경우. 바로 자신의 값을 리턴하면 됩니다. 이 경우는 구간 크기가 1인 경우도 자동으로 포함합니다.

세 번째~네 번째 줄이 그 외의 경우로 현재 노드의 구간을 양분해 각각을 재귀호출해서 더하는데, 이건 이 구간을 2등분하면 왼쪽 것은 이 노드의 왼쪽 자식, 오른쪽 것은 이 노드의 오른쪽 자식이 표현하고 있다는 걸 잘 이용한 형태입니다.

저의 경우는 구간 [L, R]이 아니라 구간 [L, R)의 형태로 짜서(즉, R은 구간에 포함 안 됨) 몇몇 식들이 조금 다릅니다.

자, 그럼 이 sum 함수의 시간복잡도가 얼마일까요?

기껏 이렇게 어려운 방법으로 구간 합을 구하고 있으니 적어도 O(N)보다는 적기를 기대합니다.

정답부터 말씀드리자면 O(logN)이고, 이는 트리의 높이가 O(logN)이라서 최대 그만큼의 연산을 하리라는 짐작에서 나옵니다.

그런데 간혹 구간이 엄청 절묘하고 예술적으로 뽑혀서 엄청 많은 수의 재귀호출을 해야 할 때가 있지 않을까요? O(logN)의 범주를 초과할 정도로...

그럴 수는 없다는 것이 중요합니다.

어떤 구간을 여러 개로 쪼개서 각 구간이 전부 세그먼트 트리상의 어떤 노드의 구간과도 같지 않게, 최대한 재귀호출이 많이 되게 만들어봅시다. 얼마나 많이 되도록 만들 수 있을까요?

이렇게 생각해 봅시다. 여태까지 예제에서 하나의 깊이에 두 번의 호출이 시도되는 경우는 봤습니다. 두 번째 그림([3, 6]의 합)의 깊이 4에서 [3, 3]과 [6, 6]이 불러진 게 그 예죠.

그럼 하나의 깊이에서 3개 이상의 호출이 시도될 수 있을까요?

그러려면 어떻게 해야 할까요? 어떤 연속된 하나의 구간을 3등분해서 각 구간이 호출되도록 만들어 봅시다.

예를 들면, 구간 [0, 5]의 합을 구하고 싶은데 깊이를 3으로 잡고 이걸 저렇게 [0, 1], [2, 3], [4, 5] 3개의 구간으로 나눠서 호출해 해결했다고 가정합니다.

근데... 이거 불가능하죠. 왜냐면 [0, 1]과 [2, 3]을 합한 구간 [0, 3]을 한번에 포함하는 상위의 노드가 엄밀히 존재하고 있습니다! 따라서 저런 호출은 절대 일어날 수가 없습니다.

이런 식으로 어떤 경우를 생각해봐도 절대 하나의 깊이에서 3개의 호출이 일어날 일이 없습니다.

따라서 호출은 많이 되어봐야 2*O(logN)번임을 알 수가 있죠!!

그럼 이제 우리를 이렇게 힘들게 만든, 어떤 원소의 값을 바꾸는 경우를 생각해 봅시다.

보통 update라는 이름의 함수나 연산으로 표현합니다.

만약 우리가 2번째 원소 -3을 어떤 값, 예를 들면 1로 바꾸었다고 합시다. 그럼 어떤 노드들의 값도 덩달아 바뀌어야 할까요?

이 노드들이죠. 2번 원소를 포함하는 구간이 있는 노드들!

이러한 노드는 각 깊이마다 단 1개이며, 그러므로 총 O(logN)개의 노드들의 값이 바뀌고

이건 리프 노드 값을 갱신한 후 부모를 찾아가며 루트까지 갱신을 계속해주면 됩니다.

그렇죠. 갱신에 필요한 시간이 O(logN)입니다!!!

원소 값을 바꾸는 연산, 구간 합을 구하는 연산 둘 다 시간복잡도가 O(logN)이므로, 값 개수 N과 쿼리 개수 Q가 주어지면 시간복잡도가 O(QlogN)이 됩니다!! 드디어 세그먼트 트리의 저력이 드러납니다.

// update
 void update(int i, int val){
        i += size;
        arr[i] = val;
        while(i > 1){
            i /= 2;
            arr[i] = arr[i*2] + arr[i*2+1];
        }
 }

update 함수는 이렇게 구현합니다. i번째 원소를 val로 갱신하라.

먼저 해당 원소가 있는 세그먼트 트리상의 진짜 노드 번호를 찾아야 합니다.

이 코드에서는 size가 값의 개수(2^K 꼴)라 가정했을 경우이고 그렇다면 size를 더해주면 그 인덱스가 되겠죠.

만약 size가 세그먼트 트리의 노드 개수였다면 size/2를 더해주면 될 것이구요.

이렇게 시작해서 i가 루트에 다다를 때까지 차례대로 부모를 방문해가며 값들을 갱신합니다. 자신의 왼쪽 자식 노드 + 자신의 오른쪽 자식 노드 값으로 갱신하면 됩니다.

맨 처음에 배열의 값을 초기화할 때도 이렇게 매번 업데이트 함수를 불러줘야 세그먼트 트리가 온전히 제작되겠죠.

아니면 초기화할 때만 리프 노드 값들만 먼저 조작해두고 그 다음 한 번에 모든 노드의 값을 깊은 곳부터 구해놓으면 연산 횟수가 줄어듭니다.

또한 세그먼트 트리의 특성상 그 크기를 2^K 꼴로 맞춰주는 게 필수적이므로 그러한 최소의 값을 찾아서 크기를 재조정해 주는 전처리도 필요합니다.

마지막으로, 필수적일 정도로 필요한 경우가 많지는 않으나 최적화에 꽤 도움을 주는 연산이 하나 더 있습니다. 바로 구축(construct) 연산입니다.

리프 노드들의 값을 미리 준 후, 이 값들로 세그먼트 트리를 구축하는 것인데 간단합니다.

void construct(){
    for(int i = MAX_ST/2-1; i > 0; --i)
        arr[i] = arr[i*2] + arr[i*2+1];
}

인덱스 [MAX_ST/2, MAX_ST)에 리프 노드들의 값이 있다고 할 때, 그 바로 위 노드들부터 인덱스가 감소하는 순으로 배열의 값을 구하는 것입니다.

값을 구할때 자신의 두 자식의 배열 값을 더해야 하는데, 인덱스가 감소하는 순으로 구하면 항상 제대로 된 값을 구할 수 있습니다.

각 노드를 한 번씩만 보니까 O(N)만에 세그먼트 트리를 만들 수 있습니다. 그냥 리프 노드를 하나하나 update하는 식으로도 구축은 가능하지만 O(NlogN)이 걸리게 됩니다. 확실히 이것보다는 빠르죠.

여튼간 이렇게 해서 구간 합, 구간 최댓값 등의 구간 정보를 매우 빠르게 구할 수 있게 되었습니다!

학교 자료구조나 알고리즘 커리큘럼에서는 잘 등장하지 않는 자료구조지만, 제가 상당히 재미있게 생각하는 자료구조이기도 하고 유용할 때도 많습니다.

BOJ[12015] : 가장 긴 증가하는 부분 수열2

세그먼트 트리를 활용할 수 있는 것 중 하나가 LIS(Longest Increasing Sequence)입니다.

어떤 수열에서 증가하는 부분 수열을 뽑을 때 그 최대 길이인데요... 이거 O(N^2) DP로 구할 수 있었죠!

그러나 인생은 만만치 않아서 대부분 O(NlogN) 알고리즘이 필요할 정도로 큰 N을 줘버립니다.

LIS를 구하는 방법은 이것 하나뿐이 아니라 이분 탐색을 사용하는 방법도 존재하는데(종만북에 짤막하게 나와 있음),

굳이 세그먼트 트리를 사용한다면 이렇게 구현할 수 있습니다.

방법은 이러합니다. A[i] = x 값들을 모두 받아서 각각 (x, i) pair들을 만든 후 x 값에 대해 오름차순 정렬합니다.

이 문제에서는 그렇지 않지만 일단은 x 값들은 전부 구분된다고 가정해보죠.

어쨌든 정렬하면 작은 x값부터 훑으면서 그게 등장하는 인덱스 i를 알 수 있게 됩니다.

이제 작은 x값부터 순회하면서, A[i]=x인 i에 대해 구간 [0, i]에 지금까지 존재하는 LIS 길이 +1이 x로 끝나는 LIS 길이입니다.

이렇게 순회하면서 등장하는 가장 큰 길이가 답입니다.

이 방법을 구현하려면 이렇게 하면 됩니다.

구간 최댓값을 구하는 세그먼트 트리를 사용합니다. 처음엔 모든 자리가 0으로 초기화되어 있습니다.

그리고 작은 x부터 순회하면서 A[i]=x인 구간 [0, i]에서 최댓값을 구하고, 그 값+1을 세그먼트 트리의 인덱스 i인 리프 노드 값으로 업데이트합니다.

이러면서 등장하는 값들 중 제일 큰 게 정답이고요.

수열이 [6, 1, 2, 7, 8, 3, 5, 4]라고 해봅시다.

수열에 등장하는 원소가 오름차순으로 [1, 2, 3, 4, 5, 6, 7, 8]이네요.

맨 처음엔 A[i]=1인 i를 방문하게 되고 그 i는 1입니다.

먼저 구간 [0, 1]의 최댓값을 보는데 0입니다. 따라서 1로 끝나는 LIS 길이는 1이고, 그 1 값을 인덱스 1에 업데이트해 줍니다.

그 다음은 A[2]=2이므로 2를 방문하는데, 구간 [0, 2]의 최댓값이 1입니다.

따라서 2로 끝나는 LIS의 최대 길이는 2고, 이걸 또 업데이트해 줍니다.

다음, A[5]=3이므로 5를 방문해서 같은 걸 합니다.

다음, A[7]=4.

그 다음은 A[6]=5니까 6을 방문하는데, 이번엔 지금까지와 달리 결과가 증가하지는 않습니다.

지금까지 보면서 알 수 있는 점은, 새로 보는 원소가 기존의 LIS 길이를 증가시키려면 그 원소가 기존의 LIS보다 뒤에 나타나야 하죠?

그걸 확인하는 것이나 다름없는 행위가 구간 [0, i]의 최댓값을 보는 겁니다. 이게 구간 [0, i] 안에만 속한 LIS의 최대 길이를 의미하고,

어차피 이번에 훑은 인덱스 i는 아직까지는 등장하지 않았으므로 구간 [0, i-1]의 최댓값과도 같은 결과일 겁니다.

이번에 훑은 값이 i-1보다 큰 인덱스니까 지금까지 찾은 구간 [0, i-1]에 속한 LIS보다 뒤에 있음도 보장되고,

x 값을 오름차순으로 방문 중이므로 지금까지 등장한 모든 값들보다도 크다는 것마저 보장됩니다.

따라서 LIS에 꼬리를 하나 달아 이를 1 늘일 수 있는 것이죠!

그 다음은 A[0]=6이니까 0을 방문하는데 보시다시피 제일 왼쪽이라 별 실적을 못 냅니다.

그 다음, A[3]=7이므로 3을 방문했습니다.

여기서 지금까지 등장한 LIS는 길이 4를 갖고 있지만 원소 7과는 전혀 상관없음을 관찰할 수 있는데

그러한 LIS 마지막 원소들은 다 7보다 오른쪽에 있기 때문이죠.

그러한 결과도 지금 세그먼트 트리는 충실하게 반영하고 있습니다.

마지막으로 A[4]=8이므로 4를 방문. 길이가 4나 되는 증가수열을 찾아냈지만 지금까지의 결과와 같네요.

최종적으로 답은 4라는 것을 알 수 있고 이건 사실 모든 연산을 끝마친 후 세그먼트 트리의 루트 값과도 같습니다.

그런데 지금까지는 중복되는 값이 없을 거라 가정하고 한 건데 만약 중복되는 값이 존재한다면 이게 답을 제대로 못 구할 수 있습니다.

문제에서는 [2, 2]를 증가수열로 치지 않기 때문(같으면 증가한 게 아님). 따라서 여기서 0번 인덱스 방문 후 1번 인덱스를 방문하면 답이 1인데 2를 구해버릴 수 있습니다.

이걸 방지하려면 중복되는 값들 중에서는 가장 큰 인덱스부터 방문하면 됩니다. 정렬할 때 애초에 그렇게 정렬해두면 됩니다. 값 오름차순 -> 인덱스 내림차순으로요.

LIS 예제를 보면서 느끼셨을 수 있지만... 세그먼트 트리 역시 막상 활용하려고 하면 좀 어렵습니다.

대체로 처음부터 세그먼트 트리를 써야하게 생겼다기보다는 뭔가 알고리즘을 구상하다가 이러이러한 연산을 빨리 해야 하는데 그게 혹 세그먼트 트리에 적합할지도 모르겠다 식의 루트로 이어지는 편...

또한 LIS도 그 자체로 쓰이거나 문제의 키가 될 때가 많아서 아예 독자적인 분야로 인식됩니다. LIS를 구하는 방법이 한 가지도 아니라서요...

또한 구간 합을 구하는 데만 미친듯이 최적화되어서 시간복잡도는 같지만 실제로 더 적은 시간과 공간을 들이는 펜윅 트리(fenwick tree)라는 게 있으며, 2^k 꼴인 N에 대해 N+1칸의 배열만을 사용합니다.

다른 이름으로 바이너리 인덱스 트리(binary indexed tree, BIT)라고도 합니다.

가끔 2차원 배열

뭐?

에 대한 구간 합을 구해야 하는

막장

문제들이 존재하는데 이때는 거의 2차원 펜윅 트리를 사용하고는 합니다.

세그먼트 트리 관련 추천 문제

2042번: 구간 합 구하기

연습 문제입니다. 문제에서 경고하듯이 배열의 자료형을 int가 아니라 64비트 정수형으로 두세요.

11505번: 구간 곱 구하기

이번엔 구간 곱을 구하는 문제입니다. 연산의 특성상 값이 커질 수 있어서 modular를 줬으니 이것만 주의하시면 됩니다.

2357번: 최소값과 최대값

이번에는 값 갱신 쿼리는 안 들어오지만 구간 최소값과 최대값을 세그먼트 트리로 구해야 합니다.

즉, 세그먼트 트리를 서로 다른 용도로 2개를 만들어서 써야 합니다.

12837번: 가계부 (Hard)

단순한 구간 합 트리입니다. 다만 오버플로우를 피하기 위해 자료형을 64bit 정수형으로 설정해야 하고,

1번 연산 해석에 주의해야 합니다. p일의 내용이 x가 되는 것이 아니라, x가 더해지는 겁니다.

12015번: 가장 긴 증가하는 부분 수열 2

위에서 설명한 문제로, 최대 LIS 길이를 찾아야 합니다.

1275번: 커피숍2

문제 자체는 굉장히 쉬운데, 꼭 x<=y이지는 않고, 입력만 int형 안이랬지 합도 int형 안이란 보장은 없습니다. 함정이 많은 문제.

2268번: 수들의 합

역시 그냥 세그먼트 트리 그 이상도 이하도 아닙니다. 다만 확인은 못해봤는데 i>j일 수도 있으니 조심하세요.

3745번: 오름세

LIS 여러 번 구하는 문제입니다.

1365번: 꼬인 전깃줄

문제에서 주어지는 입력을 배열이라 할 때 이 배열의 LIS 길이가 답입니다.

3006번: 터보소트

숫자를 1->N->2->N-1->... 순으로 방문하면서 쿼리를 날려 원하는 구간 안에 수가 몇 개 남아있는지를 세면 됩니다. 이걸 구간 합 트리로 구현할 수 있죠. 이때 세그먼트 트리 리프 노드들의 값은 1로 초기화되어 있습니다.

그 수를 원래 자리 밖으로 빼면서, 그 수가 있던 인덱스 값은 0으로 업데이트해 줍시다.

1280번: 나무 심기 (★)

일단 같은 위치에 나무가 여러 개 심어질 수도 있습니다.

세그먼트 트리의 리프 노드들의 경우 인덱스 i인 칸이 이 칸에 심어진 모든 나무들에 대해 x=0으로부터의 거리 합이라 합시다. 뭐... 나무가 k그루 심어져 있다면 항상 ki겠죠.

중요한 건 매번 나무를 심을 때마다 이 나무와 그 이전의 모든 나무들의 거리 합을 구하는 것.

이건 이번에 심을 나무의 위치를 x라 할 때,

왼쪽에 있는 나무들과의 거리 합은 cnt(0, x-1)*x - sum(0, x-1),

오른쪽에 있는 나무들과의 거리 합은 sum(x+1, MAX) - cnt(x+1, MAX)*x

임을 도출할 수 있습니다. 이 둘의 합이 비용이고, cnt는 구간 내 심어진 나무 개수고 sum은 0으로부터의 거리 합입니다.

long long을 쓰셔야 합니다. 당연히 cnt, sum은 서로 다른 세그먼트 트리로 구해야 합니다.

3653번: 영화 수집 (★)

매번 자신보다 위에 쌓여 있는 영화 개수를 구해야 하는데, 맨 위에 쌓는다는 게 좀 어렵습니다. 그럼 전체 배열의 인덱스가 바뀌어버리는 것 아닌가...?

그러나 트릭을 써서 처음부터 세그먼트 트리의 원소 개수를 2N개로 잡고, i번째로 영화를 빼내서 맨 위에 쌓을 때 N+i번 위치로 옮겨버립니다.

그리고 쿼리를 날려서 이번 영화가 있는 위치를 i라 하면 구간 [i, 2N]의 영화 개수를 구간 합 트리로 세서 반환하면 됩니다.

9345번: 디지털 비디오 디스크 (★)

이 문제는 쿼리를 곧이곧대로 받아들이면 안 됩니다. 세그먼트 트리의 리프가 각각 그 자리에 몇 번 DVD가 있는지를 나타내면 풀기 어렵습니다.

바꿔서, 세그먼트 트리의 리프가 k번이라면 k번 DVD가 어느 위치에 있는지를 저장해 두면 됩니다. 매번 L~R번 DVD가 있는 위치들 중 최솟값과 최댓값이 각각 L, R인지 확인하면 문제를 풀 수 있습니다! 한 단계 발상의 전환이 필요한 문제.

2243번: 사탕상자 (★)

전체에서 k번째로 작은 수를 찾아야 합니다. 그리고 중복되는 값이 여러 개일 수도 있네요.

이때는 구간 합 트리를 마련하고, 재귀적으로 k번째 값을 찾을 때, 자신의 왼쪽 노드 구간에 포함되는 사탕 개수가 k 초과면 왼쪽 노드를 방문해 찾고, k 이하면 오른쪽 노드를 방문하는데 이때는 (k-왼쪽 자식 노드 구간의 사탕 개수)번째로 작은 수를 찾으면 됩니다. 즉

2336번: 굉장한 학생 (★)

문제에서 정보를 너무 많이 줘서 혼란스럽고 어렵습니다.

일단 첫 번째 시험, 두 번째 시험, 세 번째 시험 등수 순으로 오름차순 정렬해놓고 첫 번째 시험 등수가 낮은 학생부터 차례대로 순회합시다.

일단 이번에 순회한 학생은 지금까지 방문한 모든 학생보다 첫 번째 시험 등수가 높으니까 조건 하나는 아예 볼 필요가 없어졌습니다. 이제 두 번째와 세 번째 시험 등수만 신경쓰면 됩니다!

즉 지금까지 순회한 학생들 중 두 번째, 세 번째 시험 등수가 모두 자신보다 낮은 학생이 한 명이라도 있는지 알아보면 됩니다!

이것을 구간 최솟값 트리로 구현합니다.

뭐?

자신보다 두 번째 시험 등수가 낮은 학생들 중, 세 번째 시험 등수 중 최솟값을 찾는 겁니다. 최솟값이니까 이 값이 자신의 세 번째 시험 등수보다 낮으면 자신은 바로 그 학생을 능가했으므로 굉장한 학생이 되는 것이죠!

이것을 구현하려면 세그먼트 트리의 각 리프 노드들이 이런 형태면 됩니다. i번 리프 노드는 2번째 시험 등수가 i인 학생의 3번째 시험 등수.

이런 식으로 먼저 구간 최솟값 쿼리를 날리고, 자신의 정보도 세그먼트 트리에 업데이트시켜 가면서 문제를 풀면 됩니다.

 

**참조**

blog.naver.com/kks227