백준 11659 - 구간합구하기 4

1) 점화식
이 문제는 그냥 1차원 배열에서의 구간합 문제입니다.
arr가 있으면 그에 따른 1 ~ n 합을 담는 배열 dp[n]을 정의하고,
p ~ q구간 합을 dp[q] - dp[p - 1]로 계산하는 방식을 사용합니다.

2) source code

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mod 10000007
#define INF 100000000
#define pb push_back
#define pi 3.141592
using namespace std;

int main(void){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int arr[101010] = {0,};
    int sum[101010] = {0,};

    int n;
    int q;
    cin >> n;
    cin >> q;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        sum[i] = arr[i] + sum[i-1];
    }
    while(q--){
        int t1, t2;
        cin >> t1 >>t2;
        cout << sum[t2] - sum[t1-  1] << "\n";
    }



    return 0;
}

그리고 구간합 문제는 1base 로 배열을 구성하는것이 효율적입니다.