문제 62
구간 더하기와 최댓값
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 l r x: $A_l, A_{l+1}, \cdots, A_r$에 $x$를 더한다. $(1 \le l \le r \le N; -10^9 \le x \le 10^9)$2 l r: $A_l, A_{l+1}, \cdots, A_r$의 최댓값을 출력한다. $(1 \le l \le r \le N)$
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
모든 쿼리를 처리하는 동안 각 원소의 절댓값은 $10^{18}$을 넘지 않는다.
출력
2 l r 쿼리마다 구간의 최댓값을 한 줄에 하나씩 출력한다.
예제 입력 1
5 7 1 3 -2 4 5 2 1 5 1 2 4 3 2 2 4 1 1 5 -2 2 1 3 1 3 3 10 2 3 5
예제 출력 1
5 7 4 9
공식 해설
구간의 모든 값에 $x$를 더하면 그 구간의 최댓값도 $x$만큼 증가한다. 이 성질로 구간 최댓값과 미전파 덧셈을 저장하는 지연 전파 세그먼트 트리를 만든다.
갱신 구간에 노드 전체가 포함되면 노드의 최댓값과 지연값에 모두 $x$를 더한다. 아직 자식까지 내려갈 필요는 없다. 나중에 일부만 갱신하거나 조회해야 할 때 지연값을 두 자식에 먼저 반영한 뒤 아래로 내려간다.
부분 갱신을 마치면 부모의 최댓값을 두 자식의 최댓값 중 큰 값으로 다시 계산한다. 질의도 포함되는 노드들의 최댓값을 합쳐 구한다. 이렇게 하면 각 노드에 저장된 값이 현재 담당 구간의 최댓값이라는 의미가 유지된다.
겹치지 않는 구간은 음의 무한대를 반환해야 한다. 원소가 모두 음수인 구간도 있으므로 $0$을 반환하면 안 된다. 음의 무한대는 실제 원소가 가질 수 있는 어떤 값보다도 작은 값으로 취급한다.
시간복잡도는 $O(N+Q\log(N+1))$, 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
구간 최댓값과 지연 덧셈을 각각 long long 배열로 둔다. 완전히 포함된 노드에 적용하는 함수는 두 값에 함께 덧셈을 반영한다. 질의에서 겹치지 않는 구간의 반환값은 numeric_limits<long long>::lowest()처럼 가능한 원소보다 작은 값으로 두되, 이 값에는 갱신량을 더하지 않는다.
C 구현
최댓값과 lazy를 long long 배열에 저장한다. 구간 밖 최댓값에 0을 반환하면 음수 배열에서 틀리므로 작은 sentinel을 사용한다. 부분 탐색 전에는 자식에 lazy를 전달한다.
Python 구현
tree와 lazy를 array('q')로 둘 수 있다. 전 원소가 음수인 구간도 있으므로 바깥 영역의 값은 충분히 작은 정수로 처리한다. 완전히 포함된 노드의 max와 lazy를 함께 올린다.
Java 구현
long[] max와 lazy를 사용한다. 부분 갱신·질의 전에는 push하고 이후 자식 max를 합친다. 원소 절댓값은 $10^{18}$까지이며, lazy 누적은 최초 값과 현재 값의 차라 long에 들어간다.
Rust 구현
max와 lazy에 i64를 사용한다. 부분 탐색 전 push하고 재귀 후 max를 다시 계산한다. 바깥 영역은 실제 값보다 작은 sentinel로 두되 그 sentinel에 갱신량을 더하는 구조로 만들지 않는다.
JavaScript 구현
갱신 후 값이 $10^{18}$까지 커지므로 초기 원소와 더할 값을 토큰에서 바로 BigInt로 읽는다. 최댓값 배열과 lazy 배열도 Array(...).fill(0n)로 두며, Float64Array를 사용하면 큰 정수의 차이가 사라진다.
두 최댓값은 a > b ? a : b로 비교한다. Math.max는 BigInt를 받지 않는다. 조회 범위 밖의 결과는 null로 구분하고 실제 겹치는 결과끼리 비교하면 음수 최댓값도 정확히 반환할 수 있다.
lazy를 자식에게 더한 뒤 부모의 lazy를 0n으로 초기화한다. 인덱스·구간 길이는 Number, 원소·lazy는 BigInt로 역할을 나누고 두 타입을 직접 더하지 않는다. 세그먼트 트리의 재귀 깊이는 $O(\log N)$이므로 일반적인 깊은 그래프 DFS와 달리 재귀로 자연스럽게 구현할 수 있다. 출력은 answer.toString()이다.