구간 가산 후 최댓값 빠르게 구하기

자바스크립트 코딩테스트 문제로 lazy-segment-tree 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm hard lazy-segment-tree 함수명: rangeAddMaxQueries 제한 시간: 500ms

문제 설명

길이가 n인 배열이 있고, 모든 값은 처음에 0입니다.

operations의 각 원소는 [left, right, value] 형태입니다. 이 작업은 배열의 left번 인덱스부터 right번 인덱스까지 모든 값에 value를 더한다는 뜻입니다.

각 작업을 수행한 직후 배열 전체에서 가장 큰 값을 구해 순서대로 반환하는 rangeAddMaxQueries 함수를 작성하세요.

제한사항

1 <= n <= 100000
0 <= operations.length <= 100000
각 작업은 [left, right, value] 형태입니다.
0 <= left <= right < n
-10000 <= value <= 10000
반환값은 각 작업 직후의 전체 최댓값을 담은 배열입니다.
매 작업마다 배열 전체를 순회하면 큰 입력에서 시간 제한을 통과하기 어렵습니다.

예시

입력: n = 5, operations = [[0, 2, 3], [1, 4, 2], [3, 3, 5]] -> 출력: [3, 5, 7]
입력: n = 4, operations = [[0, 3, -2], [2, 2, 5], [0, 1, 4]] -> 출력: [-2, 3, 3]
입력: n = 1, operations = [[0, 0, 10], [0, 0, -3]] -> 출력: [10, 7]
입력: n = 3, operations = [] -> 출력: []

힌트

구간 전체에 같은 값을 더할 때, 그 구간의 최댓값도 같은 값만큼 변합니다.
세그먼트 트리의 각 노드가 담당 구간의 최댓값을 저장한다고 생각해 보세요.
업데이트 구간이 노드 구간을 완전히 덮으면 자식까지 즉시 내려가지 않고, 나중에 필요할 때 내려보낼 값을 따로 저장할 수 있습니다.

해설

이 문제는 구간 업데이트와 전체 최댓값 조회가 번갈아 나오는 문제입니다. 작업 하나마다 실제 배열의 모든 칸을 바꾸고 다시 최댓값을 찾으면 최악의 경우 O(n * q) 시간이 걸립니다.

세그먼트 트리를 사용하면 각 노드가 담당하는 구간의 최댓값을 저장할 수 있습니다. 어떤 작업 [left, right, value]가 노드의 구간을 완전히 포함한다면, 그 노드의 최댓값에는 value를 바로 더할 수 있습니다.

하지만 매번 자식 노드 끝까지 내려가면 여전히 많은 시간이 들 수 있습니다. 그래서 Lazy Propagation을 사용합니다. 완전히 덮인 노드에는 “이 구간 전체에 아직 자식에게 내려보내지 않은 값”을 lazy 배열에 기록해 둡니다.

풀이 흐름은 다음과 같습니다.

전체 배열을 담당하는 세그먼트 트리를 만들고 모든 최댓값을 0으로 둡니다.
각 작업 [left, right, value]에 대해 구간 가산 업데이트를 수행합니다.
현재 노드 구간이 작업 구간에 완전히 포함되면 그 노드의 최댓값과 lazy 값에 value를 더합니다.
일부만 겹치면 필요할 때 lazy 값을 자식에게 내려보낸 뒤, 왼쪽과 오른쪽 자식을 재귀적으로 갱신합니다.
갱신 후 부모 노드의 최댓값은 두 자식 최댓값 중 큰 값으로 다시 계산합니다.
각 작업이 끝난 뒤 전체 구간을 담당하는 루트 노드의 값이 바로 현재 배열 전체의 최댓값입니다.

음수 업데이트도 주어질 수 있으므로 최댓값이 항상 커지는 것은 아닙니다. 예를 들어 처음에 모든 칸에 -2를 더하면 전체 최댓값은 -2가 됩니다. 따라서 “가장 큰 증가량”만 따로 관리하는 방식은 맞지 않고, 실제 구간 최댓값 변화를 자료구조 안에서 유지해야 합니다.

작업 수를 q라고 하면 각 구간 업데이트는 세그먼트 트리 높이만큼의 노드를 중심으로 처리되어 O(log n)에 수행됩니다. 전체 시간 복잡도는 O(q log n), 공간 복잡도는 트리와 lazy 배열 때문에 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과