뺄셈으로 모든 구간 합 구하기

누적 합 배열을 만드는 것은 준비 단계였습니다. 이제 진짜 효과가 나타납니다. 한 번의 뺄셈으로 어떤 구간 합에도 답할 수 있습니다. ⚡

구간 합은 큰 전체 합에서 작은 합 하나를 빼면 됩니다. 누적 합 두 값을 빼면 범위 바깥의 모든 값이 깔끔하게 상쇄됩니다.

l부터 r까지 원소의 합을 구하려면 prefix[r + 1]에서 prefix[l]을 빼면 됩니다. 이 하나의 공식은 모든 구간에 적용됩니다.

prefix[r + 1]에는 r까지의 모든 값이 들어 있고, prefix[l]에는 l 이전의 모든 값이 들어 있습니다. 두 값을 빼면 정확히 가운데 구간만 남습니다.

[3, 1, 4]의 누적 합 배열은 [0, 3, 4, 8]입니다. 인덱스 1부터 2까지의 합을 구하려면 8에서 3을 빼면 되고, 결과는 5입니다. 이는 1과 4를 더한 값과 같습니다.

각 질의는 뺄셈 한 번이면 되므로 O(1)에 실행됩니다. 질의가 천 개여도 하나의 질의당 비용은 질의 하나일 때와 같습니다.

가장 흔한 실수는 끝점의 인덱스를 잘못 쓰는 것입니다. 앞에 0을 추가했다면 항상 prefix[r + 1]을 사용해야 하며, prefix[r]을 사용하면 안 됩니다. 이 경계를 확인하십시오.

r을 포함할지 일찍 결정하십시오. 이 공식은 l과 r을 모두 포함하는 구간으로 처리하며, 대부분의 대회 문제도 이를 기대합니다.

작은 보조 함수를 사용하면 로직을 읽기 쉽게 유지하고 인덱스를 한곳에서 관리할 수 있습니다. 수식을 직접 써 넣는 대신 이 보조 함수를 활용하십시오.

전체 배열의 합을 구하려면 l을 0, r을 n - 1로 설정하여 질의하십시오. 공식은 전체 합인 prefix[n]을 반환합니다.

고정된 배열에 대해 구간 합 질의가 많이 주어지는 문제라면, 누적 합을 사용하여 질의마다 O(n) 반복문을 돌리는 대신 즉시 답을 구할 수 있습니다.

l부터 r까지의 인덱스 합을 양 끝 포함으로 구하려고 합니다.

이제 prefix[r + 1]에서 prefix[l]을 빼서 모든 구간 합을 O(1)에 구할 수 있습니다. 앞에 0을 추가했을 때의 오프셋에 주의하면 버그 없이 작성할 수 있습니다. ✅