부분합 구하기 : 누적합만 들고 있으면 된다.

 1차원, 2차원 배열에서 구간이 주어졌을 때 어떻게 부분합을 구하는지 알아봅시다. 3차원 이상인 경우에는, 포함 배제의 원리를 알고 있어야 됩니다. 그렇기 때문에, 저는 1차, 2차원 array에서 subsum, 부분합을 구하는 것만 알려드리도록 하겠습니다.

 

 

---

 먼저 누적합을 1차원에서 어떻게 구하는지 봅시다.

 

 

누적합 : 0번째 원소는 더미 데이터인 0을 채운다.

 배열 arr이 있습니다. 제가 보라색으로 칠해놓은 것은 더미 데이터를 넣는데요. 0을 넣습니다. 0에 x를 더해도 0이기 때문입니다. 즉, 0은 덧셈에 대한 역원이기 때문에 보통 0으로 초기화를 합니다. nj[x]를 다음과 같이 정의합시다. 구간 [0,x]에 있는 수들의 합. 그렇다면 nj[0]의 값은 0입니다. 아무것도 없으니까 합이 0일 수 밖에 없기 때문입니다. 그러면 [0,x]까지의 합은 어떻게 구하면 될까요? [0,x-1]까지의 합에다가 arr[x]를 더하면 될 겁니다.

 

 즉, nj[x]는 nj[x-1]의 값에다가 arr[x]를 더하면 됩니다.

 

 

 먼저 nj[1]의 값은 7이 됩니다.

 

 

 nj[2]의 값은 어떻게 구할까요? 제가 초록색으로 칠한 nj[1]에다가 노란색으로 칠한 arr[2]를 더하면 됩니다. 7에 2를 더하면 9가 되나요? 즉, 배열 arr에서, 구간 [0,2]에서의 합은 9입니다.

 

 

 nj[3]은 어떤 값을 더하면 될까요? nj[2]에 arr[3]을 더하면 됩니다. 9에 3을 더하면 12가 됩니다. 따라서, nj[3]에는 12라는 값이 채워집니다. 이것을 토대로, 구간 [s, e]의 부분합은 어떻게 구하면 좋을까요?

 

 

---

 우리는 구간 [0,x]의 부분합을 알고 있어요. 그러면, 구간 [0, e]의 부분합 또한 알고 있습니다.

 

 

 이 부분입니다. 여기서 구간 [s,e]의 부분합을 구하려면 초록색으로 칠한 부분에서, 어느 부분을 빼야 할까요?

 

 

 노란색 부분을 빼야 합니다. 이 부분은 0부터 s-1까지의 구간합으로 표현이 되기 때문에, nj[s-1]로 표현을 할 수 있습니다. 즉, 구간 [s,e]의 합을 구하기 위해서는 nj[e]에서 nj[s-1]을 빼면 됩니다. 2차원에서는 어떻게 구하면 좋을까요?

 

 

---

 일단, 1행 1열부터 r행 c열까지 숫자가 채워져 있다고 합시다. 그러면 nj[r][c]는 r이 0이거나 c가 0인 경우에는 무조건 0이 될 거에요. 우리는 nj[x][y]를 다음과 같이 정의할 거에요. 0행 0열부터, x행 y열까지 누적합.

 

 

 이걸 구하려면 먼저 노란 부분의 합을 구해야 합니다. 이는 nj[x-1][y]로 표현할 수 있어요.

 

 

 다음에 초록색으로 칠한 부분의 합을 구해야 합니다. 이는 nj[x][y-1]을 참조하면 됩니다. 그런데, 노란색 부분하고, 초록색 부분하고 공통된 부분이 있는 거 같습니다. 일명, 겹치는 부분입니다. 어디인가요?

 

 

 보라색으로 칠한 부분입니다. 여기가 겹치는 부분인데요. 이 부분을 빼야 합니다. 즉, nj[x-1][y-1]을 빼야 합니다. 그러면, arr[x][y]를 제외한 0행 0열부터 r행 c열까지의 합이 구해집니다. 여기에, arr[x][y]를 더하면 됩니다. 정리하면, nj[x][y]의 값은 nj[x-1][y] + nj[x][y-1] - nj[x-1][y-1] + arr[x][y]로 구할 수 있습니다.

 

 

---

 그러면 구간 (x1,y1)에서 구간 (x2,y2)까지의 합은 어떻게 구하면 좋을까요?

 

 

 즉, 자홍색 부분에 있는 수들의 합은 어떻게 구하면 좋을까요? 천천히 생각해 봅시다. 먼저 nj[x2][y2]를 구해 봅시다.

 

 

 그러면, 이 때는 (0,0)부터 (x2,y2)까지의 부분합을 구하는 것입니다. 하늘색으로 칠한 부분 전체의 합을 구하는 것입니다. nj[x2][y2]에서 무언가를 빼야 할 듯 싶네요. 어떤 것을 빼 보면 좋을까요?

 

 

 노란 색으로 칠한 부분을 먼저 빼 봅시다. 0행 0열부터 x1-1행 y2열까지의 합은 nj[x1-1][y2]로 표현이 됩니다. 그런데 이것만 빼서는 뭔가 부족할 거 같아요. 무엇을 더 빼야 할까요?

 

 

 초록색 부분을 빼야 해요. 즉 0행 0열부터 x2행 y1-1열까지의 합은 nj[x2][y1-1]로 표현이 되는데요. 이것도 nj[x2][y2]로부터 빼야 합니다. 그런데, 무엇인가가 중복해서 빠진 거 같지 않나요?

 

 

 보라색 부분이 추가로 한 번 빠졌기 때문에, 이 부분을 더해줘야 합니다. 이 부분이 두 번 빠진 부분이기 때문입니다. 보라색 부분에 들어있는 수들의 합은 nj[x1-1][y1-1]로 표현이 될 수 있어요. 즉, nj[x2][y2]에서, nj[x2][y1-1] + nj[x1-1][y2] - nj[x1-1][y1-1]의 값을 빼 주면, x1행 y1행부터, x2행 y2행까지의 수들의 합을 구할 수 있어요.