[백준 10999번] 구간 합 구하기 2

난이도: 플래티넘 IV

문제 링크: https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

 

백준 10999번 문제 구간 합 구하기 2

 

그냥 접근하면 시간 초과에 걸리고, 세그먼트 트리를 이용해도 시간 초과에 걸리는 문제입니다.

이 문제를 풀려면 '느리게 갱신되는 세그먼트 트리' 알고리즘을 알아야 합니다.

해당 알고리즘에 대한 자세한 설명은 여기에 있으니 참고해 주세요.

 

문제를 풀 때 유의할 점은,

문제에서 숫자 배열의 인덱스는 1부터 시작합니다. 무심코 숫자를 배열에 그대로 담는다면 인덱스가 0부터 시작하므로 의도와 다른 결과가 나올 수 있습니다.

또한 값을 수정할 때, 꼭 재귀적으로 부모 노드의 값을 갱신해야 합니다!

자식 노드의 값이 lazy를 반영하여 수정되었다면, 부모 노드 역시 값이 갱신되어야 함을 잊지 마세요.

 

채점 결과

문제를 푼지는 좀 됐는데...

블로그에 세그먼트 트리에 대한 글을 먼저 올려야 할 것 같아서 실제로 블로그에 올리기에는 조금 더 시간이 걸렸네요.

맨 처음에는 평범한 세그먼트 트리를 이용해 풀었고, 당연히 시간초과에 걸렸습니다.

두 번째에는 부모 노드의 값을 재귀적으로 갱신하지 않아 오답 판정을 받았고, 이를 수정하니 세 번째에는 정답 판정을 받았네요.