누적 합

이러한 인덱싱에서는 다음 사항에 유의하십시오

• $s_k$는 $a_k$를 포함하지 않는 배열 $a$의 처음 $k$개 원소의 합과 같으며,
• $s$의 길이는 $a$의 길이보다 1만큼 깁니다,
• $s_0$은 항상 0입니다.

때로는 누적 합을 오른쪽 끝을 포함하고 0번째 원소 없이, 즉 $s_k = a_0 + a_1 + \ldots + a_k$로 정의하기도 합니다. 하지만 닫힌 구간이 반열린 구간보다 거의 항상 덜 편리한 것과 같은 이유로, 우리는 항상 정의에 따른 ‘반열린 구간’ 방식의 누적 합을 사용하겠습니다.

$s_k$에 대한 공식은 $s_{k+1} = s_k + a_k$와 같이 점화식으로 쓸 수 있으며, 이로부터 누적 합을 선형 시간에 계산하는 방법을 곧바로 얻을 수 있습니다.

int s[n + 1];

s[0] = 0;

for (int i = 0; i < n; i++)
    s[i + 1] = s[i] + a[i];

문제. 정수 배열이 주어지고, 「위치 $l$부터 위치 $r$까지의 반구간에서 합을 구하라」 형태의 쿼리가 들어옵니다. 쿼리에 $O(1)$에 답해야 합니다.

쿼리에 답하기 전에 원래 배열에 대한 누적 합 배열을 미리 계산해 둡시다. 그러면 모든 쿼리에서 $l$이 0이라면, 쿼리의 답은 단순히 누적 합 $s_r$일 것입니다. 그런데 $l \neq 0$이라면 어떻게 해야 합니까?

누적 합 $s_r$에는 우리에게 필요한 모든 원소가 들어 있지만, 불필요한 원소들도 함께 들어 있습니다. 바로 $a_0, a_1, \ldots, a_{l - 1}$입니다. 이러한 합은 다시 이미 계산해 둔 누적 합 $s_l$과 같다는 점에 주목하십시오. 따라서 다음 항등식이 성립합니다.

임의의 반구간에서 합을 구하는 쿼리에 답하려면 미리 계산해 둔 두 누적 합의 차를 구하기만 하면 됩니다.

#기타 연산

이와 같은 기법은 덧셈뿐만 아니라 다른 연산에도 사용할 수 있습니다.

여기서 우리가 덧셈에 실제로 필요로 했던 것은 무엇입니까? 덧셈에 역연산인 뺄셈이 있다는 점뿐입니다. 뺄셈을 이용하면 $s_l$을 “취소"하여 두 접두사로부터 구간의 값을 복원할 수 있습니다. 합은 역연산이 가능하지만, 예를 들어 최솟값이나 최댓값은 역연산이 불가능합니다. 일반적인 경우 접두사의 최솟값들로부터 구간의 최솟값을 구하는 것은 불가능합니다(배열의 첫 번째 원소가 최솟값인 경우를 생각해 보면 쉽게 확인할 수 있습니다. 이때 모든 누적 합은 그 원소와 같아지므로 나머지 값들에 대한 모든 의존성이 사라집니다).

덧셈 외에도 역연산이 가능한 연산이 있습니다:

• 비트 단위 배타적 「논리합」, 즉 xor로도 알려져 있으며 $\oplus$로 표기하는 연산,
• 모듈러 덧셈,
• 곱셈과 모듈러 곱셈(역연산은 나눗셈).

일반적인 합 외에 가장 많이 쓰이는 것은 xor이며, 이는 훨씬 더 간단하게 계산됩니다:

#누적 합 문제

문제. 정수 배열이 주어집니다. 이 배열에 주어진 합을 갖는 부분 구간이 있는지 선형 시간에 판별하십시오.

문제. 길이가 같은 두 배열이 주어집니다. (해당 구간의 인덱스에서) 첫 번째 배열의 원소 합과 두 번째 배열의 원소 합이 같아지는 부분 구간을 찾으십시오.

문제. $n$개의 정수로 이루어진 멀티셋이 주어집니다. 원소의 합이 $n$으로 나누어떨어지는 부분집합을 아무거나 하나 찾으십시오.