어떠한 앞에서부터 요소까지 계속 더한거 말하는거임.

뒤에서 부터 더하는것은 suffix sum이다.

문제

범위가 1~4, 1~5, 3~5까지의 누적합들을 구해라라는 문제임

그래서 코드를 이렇게 짜면 틀림.

10만 * 10만은 100억임. int범위를 벗어난다.

그러면 long long으로 하고 푸나? 풀리기야할듯?

근데 이때 사용하는 알고리즘이 "누적합"이다.

이런 구간을 정하는게 "구간합 쿼리"이다.

구간에 대한 합을 구해달라는 요청이기 때문에.

또한 이문제는 배열의 요소가 변하지 않는 정적배열 이라 psum사용가능함.

배열의 요소가 바뀐다면 펜윅 써야함.

psum코드

이해는 간다. 뭔가 DP랑 비슷한거같은듯?

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
#define MAX 201
#define Moduler 1000000000
#define endl "\n"

int nums, loop;
ll arr[100001];
ll psum[100001];

int main()
{	
	cin >> nums >> loop;

	for (int i = 1; i <= nums; ++i)
	{
		cin >> arr[i];
		psum[i] = psum[i - 1] + arr[i];
	}

	int left, right;
	for (int i = 1; i <= loop; ++i)
	{
		cin >> left >> right;

		cout << psum[right] - psum[left - 1] << endl;
	}

	return 0;
}