[누적합] 백준 11659 구간 합 구하기 4 C++

※ 문제

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

※ 풀이

dp[i] := 1부터 i까지 배열 합 저장

∴ i부터 j까지의 구간 합 : dp[j] - dp[i] (i <= j)

#include<cstdio>

using namespace std;

int n, m, p, q, sum;
int a[100001];
int dp[100001];

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
        dp[i] = sum; // 1부터 i까지 배열 합 저장
    }

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &p, &q);
        printf("%d\n", dp[q] - dp[p - 1]); (q) 배열 합 - (p-1) 배열 합
    }
}