[알고리즘]-계차 누적합 계산

계차와 누적합

정수 $A_1, A_2, ···, A_N$ 이 있을 때,

계차는 수열에서 인접한 항들 간의 차이를 나태낸다.
$B_i=A_i - A_{i-1}$

누적합은 각 항의 값들을 차례로 더한 결과를 타나낸다.
$B_i=A_1 + A_2 + ··· + A_N$

3	4	8	9	14	23

의 계차와 누적합은 아래와 같이 된다.

3	1	4	1	5	9

계차

3	7	15	24	38	61

누적합

계차와 누적합은 서로 반대로 생각할 수 있다.
예를 들어서

3	4	8	9	14	23

의 계차는

3	1	4	1	5	9

이고

3	1	4	1	5	9

의 누적합은

3	4	8	9	14	23

이렇게 나타난다.

다른 예에서도 이 성질이 성립이 된다.

Ex.1

3	4	8	9	14	23

$↑누적합 / ↓계차$

3	1	4	1	5	9

Ex.2

1	5	6	10	12	13

$↑누적합 / ↓계차$

1	4	1	4	2	1

계차는 직접 계산을 하여도 복잡도 $O(N)$으로 구할 수 있다. 하지만 누적합을 직접 계산하면 $B_1$을 구하기 위해서 1번의 덧셈, $B_2$를 수하기 위하여 2번의 덧셈, ···, $B_N$을 구하기 위하여 $N$번을 더해야 하므로, 합계 계산 횟수는 $N(N+1)\div 2$회가 된다. 따라서 복잡도는 $O(N^2)$가 된다.

이때 누접합이 계차의 반대라는 것을 사용하여 다음과 같은 순서로 계산을 한다면, 복잡도 $O(N)$으로 계산이 된다

$B_1=A_1$
$i=1, 2, 3, ․․․, N순서이다.

	$A_1$	$A_2$	$A_3$	$A_4$	$A_5$	$A_6$
원래 배열	3	1	4	1	5	9
	↓+	↓+	↓+	↓+	↓+	↓+
누적합	3	4	8	9	14	23
	+→	+→	+→	+→	+→

---

예제 문제

누적합

• 입장 인원 계산하기

  $N$일 동안 진행이 되는 행사에서 $i$번째 날에 $A$명의 인원이 입장할 예정이다. 질문 $Q$개의 답을 하시오.
  $Q_1.$ $L_1$번째 날에서 $R_1$ 날 까지의 입장객의 수는?
  $Q_2.$ $L_2$번째 날에서 $R_2$ 날 까지의 입장객의 수는?
  …
  $Q.$ $L_Q$번째 날에서 $R_Q$ 날 까지의 입장객의 수는?

  일단 이러한 문제를 해결하는 방법으로는 가장 간단하게 직접 계산을 하는 방법이 있다. 하지만 하나의 질문에 대하여 최대 $N$번의 덧셈을 해야한다. 그리고 질문이 모두 $Q$개 이므로 복잡도가 $O(NQ)$가 된다.

  좀 더 좋은 방법으로는 2가지 방법이 있다.

• $x$번째 날에서 $y$ 번째 날 까지의 누적 입장 수

• [$y$번째 날까지의 누적 입장 수] - [$x-1$번째 날까지의 누적합 수]

  [$A_1,$ $A_2,$ $A_3,$ $...,$ $A_N$]의 누적합을 [$B_1$, $B_2$, $B_3$, $...,$ $B_4$] 라고 할 때

$N$ 번째 질문의 답은 $B_{R_N}-B_{L_{N-1}}$이 된다.
예를 들어 입장 수를 $3, 1, 4, 1, 5, 9, 2, 6$ 라고 가정을 하자
그러면 누적 입장자 수를 나타내면

	3	1	4	1	5	9	2	6
누적합	3	4	8	9	14	23	25	31

여기서 3일차에서 6일차 까지의 입장한 수를 확인을 하면
$4+1+5+9=19$ 해당 기간 동안의 누적 입장 수는 $19$가 된다.

누적합을 이용하여 계산을 하면,
6일차 동안의 누적 입장수 - 2일차 동안의 누적 입장 수 를 계산하면 된다.
$23-4=19$

각 일차의 입장수를 계산하는 방법 보다 훨 빠르게 답을 구할 수 있다.

이렇게 된다면 복잡도는 $O(N+Q)$로 정답을 구할 수 있다.

---

계차

• 눈 시물레이션

  특정 나라에 여러 지역이 있다. 해당 나라에서 지역 명칭을 서쪽에서 동쪽 방향으로 $1$ ~ $N$으로 지정했다.
  모든 지역에서 눈이 쌓여있지 않은 상태에서 어느날 $Q$일 동안 눈이 쌓였다.
  $i$번째 날에 지역 $L_i, ..., R_i$에 눈이 $Xcm$만큼 쌓일거라 예상이 된다고 한다.
  예상대로 눈이 모두 내리고 눈이 얼마나 쌓였는지 대소 관계를 나타내야 한다. $N-1$문자의 문자열을 출력하는 프로그램을 작성하라
  $i$ 번째 문자는 다음을 의미한다.
  (지역 $i$에 쌓인 눈) > (지역 $i+1$에 쌓인 눈) => >
  (지역 $i$에 쌓인 눈) = (지역 $i+1$에 쌓인 눈) => =
  (지역 $i$에 쌓인 눈) < (지역 $i+1$에 쌓인 눈) => <

지역$i$의 현재 적설량을 $A_i$로 나타내는 배열을 만들고 차례대로 값들을 더해서 $A_i$를 구한 뒤 비교하는 방법을 생각을 할 수 있겠지만, 각 날에 최대 $N$번 덧셈을 해야하고 이를 $Q$일 동안 반복을 해야한다.
이 처럼 계산을 하게 된다면 복잡도는 $O(NQ)$가 된다.

보다 좋은 방법으로 계차를 사용을 한다면

'지역 $i$에 쌓인 눈' 에서 '지역 $i-1$에 쌓인 눈'을 뺀 값을 $B_i$라고 나타낸다면, 지역 $l$부터 $r$까지에 쌓인 눈을 $xcm$만큼 증가 시키는 조작은

• $B_i$의 값을 $x$만큼 증가시키고, $B_{r+1}$의 값을 $x$만큼 감소 시킨다.

눈의 양 $[A_1, A_2, ..., A_N]$과 계차$[B_1,B_2, ..., B_N]$으로 나타낼 수 있다.

날짜/지역	1	2	3	4	5	6	계차 ➡️	1	2	3	4	5	6
0	0	0	0	0	0	0		0	0	0	0	0	0
1-지역 2~5에 4cm	0	4	4	4	4	0		0	4	0	0	0	-4
2-지역 1~6에 3cm	3	7	7	7	7	3		3	4	0	0	0	-4
3-지역 5~6에 2cm	3	7	7	7	9	5		3	4	0	0	2	-4
4-지역 3~6에 6cm	3	7	13	13	15	11		3	4	6	0	2	-4

추가적으로 "지역$i$에 쌓인 눈"과 "지역$i+1$에 쌓인 눈"의 대소 관계는 $B_{i+1}>0$인지 판정을 할 수 있다. 따라서 계차 $B_i$를 배열로 만들어두고 물음에 맞게 계산하는 프로그램을 구성하면 해당 문제를 복잡도 $O(N+Q)$로 답을 구할 수 있다.