# 누적합

📌누적합이 언제 효과적일까요??

아래 문제를 함께 봅시다.

{% embed url="<https://www.acmicpc.net/problem/11659>" %}

직관적으로 우리가 짤 수 있는 코드는 다음과 같습니다.\
그냥 l과 r을 입력받아서 arr에서 차례대로 원소를 가져와 sum에 더하면 되겠죠?

```python
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
arr = [*map(int,input().split())]

for i in range(m):
    l, r=map(int,input().split())
    ans=0
    for j in range(l-1,r):
        ans+=arr[j]
    print(ans)
```

그런데 11659가 요구하는 시간제한은 1초로 1억번의 연산 안에 통과해야 합니다.\
극단적인 경우 위 연산은 O(NM)일텐데 N과 M 모두 100,000이므로 통과할 수 없습니다.

이럴 때 누적합을 사용합니다.

📌  1차원 누적합\
아이디어만 중요할 뿐 그리 어려운 로직은 아닙니다.

![](/files/6RE76WYvkZlHln6iZoMM)고등학교 때 많이 본 이 로직과 비슷합니다.

일단 기존 arr가 있다면 피보나치 수열 형태로 prefix\_sum을 만듭니다.

![](/files/4vpHSjy6CwTfMK45Y4La)![](/files/TzKhZn7KWuV5fhRFxdz9)

arr\[2]+arr\[3]에 해당하는 부분합은 prefix\_sum\[3]-prefix\_sum\[1]을 하면 자동적으로 구해지는 것을 증명할 수 있습니다.

<pre class="language-python"><code class="lang-python">#누적합
#완전탐색은 O(NM)인데 누적합은 O(N+M)이다
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
arr = [*map(int,input().split())]

psum=[0]*(n+1)
for i in range(1,n+1):
    psum[i]=psum[i-1]+arr[i-1]

<strong>for i in range(m):
</strong>    l, r=map(int,input().split())
    print(psum[r]-psum[l-1])
</code></pre>

📌2차원 - 2167\
이번에는 누적합을 이차원으로 구현하는 방법에 대해 알아봅시다.

{% embed url="<https://www.acmicpc.net/problem/2167>" %}

이차원 누적합의 초기화 단계는 다음과 같습니다.

①A(i, j)에서 행방향으로 누적합을 구합니다\
②행 누적합에 대해서 열방향으로 누적합을 구합니다.

이 때 우리가 고등학교 때 배웠던 세 집합의 합집합을 구하는 공식과 비슷한 로직이 들어갑니다.

![](/files/15UTkth0euNrUbnPE6wV)A∪B∪C = A+B+C-A∩B-A∩C-B∩C+A∩B∩C 기억하죠?

다음과 같은 표 A의 누적합을 구하고 싶습니다.

| 1 | 4 | 4 | 9 |
| - | - | - | - |
| 3 | 2 | 7 | 6 |
| 5 | 2 | 8 | 8 |

먼저표 A보다 행과 열이 각각 1개씩 많은 표 prefix\_sum를 만들고 0행과 0열을 모두 0으로 초기화시킵니다.

<table><thead><tr><th></th><th width="137"></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>0</td><td></td><td></td><td></td><td></td></tr></tbody></table>

이후 **prefix\_sum\[i]\[ j]=prefix\_sum\[i-1]\[j]+prefix\_sum\[i]\[j-1]-prefix\_sum\[i-1]\[j-1]+A\[i]\[j]**&#xB97C; for문으로 처리해주면 아래와 같이 우리가 의도한 대로 열 방향/행 방향 누적합이 모두 적용됩니다.

<table><thead><tr><th></th><th width="112"></th><th width="139"></th><th></th><th></th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>5</td><td>9</td><td>18</td></tr><tr><td>0</td><td>4</td><td>10</td><td>12</td><td>36</td></tr><tr><td>0</td><td>9</td><td>17</td><td>36</td><td>59</td></tr></tbody></table>

그럼 이번에는 prefix\_sum 배열에서구간합을 구해볼까요?\
다아래2차원 배열에서 파란색에 해당하는 구간을 구하고 싶다고 합시다.

<figure><img src="/files/u5I4sbGJ0x8wNimZ4jaR" alt=""><figcaption></figcaption></figure>

이 때 우리가 고등학교 때 배웠던 3개의 집합의 교집합을 구하는 공식과 비슷하게&#x20;

파란색 부분=  전체합 - 초록색1 - 초록색2 + 빨간색 \
으로 구할 수 있습니다.

```python
N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]
prefix_sum=[[0 for i in range(0,M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        prefix_sum[i][j]=prefix_sum[i][j-1]+prefix_sum[i-1][j]
                            -prefix_sum[i-1][j-1]+A[i-1][j-1]

for _ in range(int(input())):
    i, j, x, y =map(int,input().split())
    print(prefix_sum[x][y]-prefix_sum[x][j-1]-prefix_sum[i-1][y]+prefix_sum[i-1][j-1])
```

사실 1,2차원 누적합은 이해한 후에, 공식처럼 외우고 응용에 써먹는 게 중요합니다. \
연속적인 어떤 구간에서 어떤 처리를 하고자 한다면 의심해보면 좋습니다.&#x20;

## 풀어볼 문제

'연속적인 어떤 구간'이 나온다면 의심해보는 것이 좋습니다.

{% embed url="<https://www.acmicpc.net/problem/19951>" %}

{% embed url="<https://school.programmers.co.kr/learn/courses/30/lessons/72414>" %}
카카오 코테 기출
{% endembed %}

{% embed url="<https://school.programmers.co.kr/learn/courses/30/lessons/92344>" %}
누적합 역행 아이디어성 문제
{% endembed %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://koalas-organization.gitbook.io/koala_codingtest_study/prefixsum_and_twopointer/prefix_sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.