더블릿 sumofinte - 연속 구간 합

문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php

정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..

문제

수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q <= 200,000이다.
Q개 줄의 입력이 주어지는 데, 입력이 0 a b 형태면 a번째 숫자를 b로 바꾸고, 1 이면 연속된 숫자들의 최대 합을 출력한다.

전형적인 세그먼트 문제이겠거니 풀려다가 코 깨졌다. 추석에 시간이 널널해서 여유롭게 풀었다.

세그먼트 트리에서 각 노드가 포함하는 범위에 대해 연속 구간의 최대 합을 저장하는 데, 네 구간으로 쪼개서 저장한다.

1. 왼쪽 구간에서 나올 수 있는 최대 합
2. 오른쪽 구간의 최대 합
3. 중간 어떤 구간의 최대 합
4. 전체 구간의 합

검은색 노드를 현재 노드라고 했을 때, 왼쪽 자식 노드와 오른쪽 자식 노드를 L과 R로 표시하겠다.
~~.left는 왼쪽 구간의 최대 합 ~~.right는 오른쪽 구간의 최대 합, ~~.middle은 중간 구간의 최대 합 그리고 ~~.sum은 그 노드 아래의 전체 구간의 합이라는 의미로 사용했다.
즉, L.right 이라면 왼쪽 자식에게서 구해지는 오른쪽 구간의 최대 합이란 뜻이다.

1. 왼쪽 구간에서 나올 수 있는 최대 합

위와 같이 세 가지의 경우가 있다. 왼쪽 자식의 왼쪽 구간, 왼쪽 자식의 전체 합, 왼쪽 전체와 오른쪽 자식의 왼쪽 구간까지의 최대 합.
왼쪽 구간이라는 게 어떤 노드가 구간 [a, b]에 대한 노드라면, 최대 합이 나올 수 있는 구간 [a, ?]를 저장하겠다는 의미이다.
코드로 적으면 아래와 같다.

2. 오른쪽 구간의 최대 합

오른쪽은 왼쪽의 좌우 반전으로 처리하면 된다. 
반대로 최대 합이 나올 수 있는 구간 [?, b]를 찾는다.

3. 중간에서 나올 수 있는 최대 합

왼쪽 자식이 구한 중간과, 오른쪽 자식이 구한 중간을 비교해서 더 큰 것이 현재 노드의 (중간에서 나오는 형태 중) 가능한 최대 합이다.

근데 그냥 이렇게만 하면 놓치는 경우가 생긴다. 바로 이런 모양이다.

빨간색으로 표시한 구간이 정답인 경우는 놓치고 만다. 
그러니 다음과 같은 경우도 middle을 계산할 때 고려하자.

여기서 그냥 L.right + R.left만 하는 이유는, 위(1번, 2번)에서 이미 L.right가 L.L.right + L.R.right 과 L.R.sum 중 최대 합인 경우를 처리했기 때문이다.

4. 전체 구간의 합

this->sum = L.sum + R.sum