184. Continuous Sum Segment Tree

DP로 해결할 수 있는 문제 중 수열에서 최대 연속합을 구하는 문제가 있다. 이전에 소개한 적이 없으므로 여기서 소개를 하자면 다음과 같다. 아래 문제를 보자.

 

BOJ 1912. 연속합 (Silver II)

$n$개의 수가 주어지고 그것을 각각 $a_1, a_2, \ldots, a_n$이라고 했을 때 두 인덱스 $i$와 $j$를 잘 정해서 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$가 최대가 되도록 해야 한다. 세 번째 예제에서 볼 수 있듯이 모든 수가 음수인 경우에도 최소 하나의 수를 골라야 한다.

 

이 문제를 DP로 풀기 위해 식을 세워 보자. $j$가 $1$인 경우부터 $n$인 경우까지 각각에 대해 해당 조건에서의 최대 연속합 $m_j$를 구하고 거기서 가장 큰 값을 찾으면 된다.

 

먼저 원소를 한 개 이상 선택해야 하므로 $m_1 = a_1$이다. 다음으로 $j > 1$인 경우의 최대 연속합은 일단 $a_j$는 포함해야 하고 앞에서 몇 개의 연속된 원소를 더 선택하는 경우 $m_{j - 1}$이 앞쪽의 최대 연속합이다. 이때 이 값이 음수일 수도 있으므로 $m_j = \max(0, m_{j - 1}) + a_j$가 최종 식이 된다. $m_0 = 0$으로 두면 이 식은 $j = 1$일 때도 성립한다.

 

이제 이 점화식을 그대로 구현하면 $\Theta(N)$ 시간에 문제를 풀 수 있다. 진짜 문제는 여기서부터 시작하는데, 문제를 푸는 사람들을 항상 괴롭게 하는 '값 변경 + 쿼리 추가' 세트를 여기에도 추가해 보자. 대충 이런 쿼리 문제가 된다. 마찬가지로 $n$개의 수 $a_1, a_2, \ldots, a_n$이 있고,

• $1\ x\ y$: $a_x$를 $y$로 바꾼다.
• $2\ x\ y$: $x$번째 수 ~ $y$번째 수들 중 가장 큰 연속합을 출력한다.

$2$번 쿼리를 조금 더 자세하게 풀면 $x \le i \le j \le y$를 만족하는 쌍 $(i, j)$ 중 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$의 최댓값을 찾으라는 것이다. 쿼리의 수가 $q$일 때 앞에서 소개한 방법으로 전체 문제를 풀면 $O(nq)$의 시간복잡도가 나올 것이다. 이제 세그먼트 트리를 이용하여 시간복잡도를 줄이는 방법을 알아보자.

---

연속합 세그먼트 트리(Continuous Sum Segment Tree)는 연속합을 빠르게 구하는 용도로 사용되는 세그먼트 트리이다. 각각의 노드에 구간이 대응하는 것은 일반적인 세그먼트 트리와 동일하고, 노드마다 아래의 $4$개 값을 저장한다.

• $i$번 노드에 대응하는 구간에서의 최대 연속합 $a_i$
• $i$번 노드에 대응하는 구간에 속하는 원소들의 합 $s_i$
• $i$번 노드에 대응하는 구간의 첫 번째 원소를 포함하는 최대 연속합 $l_i$
• $i$번 노드에 대응하는 구간의 마지막 원소를 포함하는 최대 연속합 $r_i$

세그먼트 트리를 초기화하거나 원소의 값을 바꿀 때 이 값들은 다음과 같이 계산할 수 있다. 이전에 $x$번 노드의 자식을 $2x$번과 $(2x + 1)$번 노드로 둔다고 했던 것을 참고하라.

• $a_i = \max(a_{2i}, a_{2i + 1}, r_{2i} + l_{2i + 1})$
• $s_i = s_{2i} + s_{2i + 1}$
• $l_i = \max(l_{2i}, s_{2i} + l_{2i + 1})$
• $r_i = \max(r_{2i + 1}, r_{2i} + s_{2i + 1})$

식이 왜 이렇게 되는지는 각자 생각해 보자. 위쪽에 나온 기본 연속합 문제의 식과 연관지어 보면 알 수 있을 것이다.

 

이 식을 이용해서 원소의 값을 바꾸는 쿼리를 처리할 수 있고, 구간에서의 최대 연속합을 구하는 쿼리도 처리할 수 있다. 다음과 같은 과정을 거치게 된다.

    1. 루트 노드에서 탐색을 시작한다. 현재 탐색하는 노드를 $x$라고 하자.

    2. 현재 노드에 대응하는 구간이 연속합을 구하는 구간에 완전히 포함되는 경우 $\{a_x, s_x, l_x, r_x\}$를 반환한다.

    3. 현재 노드에 대응하는 구간이 연속합을 구하는 구간에 하나도 포함되지 않는 경우 $\{-\infty, -\infty, -\infty, -\infty\}$를 반환한다.

    4. 현재 노드에 대응하는 구간이 연속합을 구하는 구간에 일부만 포함되는 경우 먼저 양쪽 자식 노드를 탐색하고 반환값들을 얻는다. 이 값을 바탕으로 $4$개의 값을 앞에서 나온 식을 이용하여 계산한 다음 반환한다.

    5. 루트 노드의 반환값 중 첫 번째 값이 쿼리의 답이 된다.

 

4번을 제외한 나머지 과정은 쉬운 말로 설명되어 있다. 4번 과정은 그것들보다는 약간 복잡한 말로 설명되어 있지만 어려운 부분이 아니므로 구현을 보면서 이해하기로 한다. 먼저 원소의 값을 변경하는 함수이다.

int p = 1 << 17, a[1 << 18], s[1 << 18], l[1 << 18], r[1 << 18];
void REP(int i, int v)
{
    i += p;
    a[i] = s[i] = l[i] = r[i] = v;
    
    for(; i >>= 1; )
    {
        a[i] = max({a[i << 1], a[i << 1 | 1], r[i << 1] + l[i << 1 | 1]});
        s[i] = s[i << 1] + s[i << 1 | 1];
        l[i] = max(l[i << 1], s[i << 1] + l[i << 1 | 1]);
        r[i] = max(r[i << 1] + s[i << 1 | 1], r[i << 1 | 1]);
    }
}

 

다음은 구간의 최대 연속합을 구하는 함수이다. 매개변수 $x$와 $y$는 항상 같으므로 전역 변수 등으로 적당히 빼도 상관없다.

struct data{int a, s, l, r};
data getMax(int x, int y, int d, int ll, int rr) // x번째 원소부터 y번째 원소까지의 최대 연속합을 구해야 하고, 현재 노드 d에 대응하는 구간이 [ll, rr]인 경우
{
    if(x <= ll && rr <= y)return {a[d], s[d], l[d], r[d]};
    if(rr < x || y < ll)return {-1 << 30, -1 << 30, -1 << 30, -1 << 30}; // return -infty
    data v1 = getMax(x, y, d << 1, ll, ll + rr >> 1), v2 = getMax(x, y, d << 1 | 1, ll + rr + 1 >> 1, rr);
    return {max({v1.a, v2.a, v1.r + v2.l}), v1.s + v2.s, max(v1.l, v1.s + v2.l), max(v1.r + v2.s, v2.r)};
}

 

이제 두 쿼리 모두 개당 $O(\lg N)$ 시간에 처리할 수 있다.

 

[연습문제]

 

BOJ 16993. 연속합과 쿼리 (Platinum I)

기본적인 문제이다. 값을 바꾸는 쿼리가 없기 때문에 연속합을 구하는 쿼리만 잘 처리해주면 된다.

 

BOJ 10167. 금광 (Diamond V)

$x$좌표를 기준으로 시작점과 끝점을 고정하고 그 구간에 속하는 점들에 대해 최대 연속합을 구하는 과정을 반복하면 된다. 시작점과 끝점은 점이 있는 좌표만 해 보면 되므로 $O(N^2 \lg N)$ 시간에 문제를 풀 수 있다. 한국에서는 이 문제가 연속합 세그먼트 트리의 대표적인 문제로 유명한 관계로 이 세그먼트 트리를 금광세그라고 부르는 경우도 많다.