[BOJ] 11659 구간 합 구하기 4

구간 합 구하기 4
https://www.acmicpc.net/problem/11659

1부터의 누적합을 dp로 저장하여 뺄샘연산을 통해서 구간합을 구하였다.

단순한dp문제지만 힙,인덱싱트리 등을 배우고나서 풀라니까 너무 복잡하게 생각했던문제

#include <bits/stdc++.h>
using namespace std;


int N, M;
int arr[100001];
	
int dp[100001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;

	
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		if (i == 1) dp[1] = arr[1];
		else dp[i] = dp[i - 1] + arr[i];
	}
	


	for (int i = 1; i <= M; i++) {
		int l, r;
		cin >> l >> r;
		cout << dp[r] - dp[l - 1] << "\n";
	}


	return 0;
}