[230131] 구현 문제 prefix_sum

const 구간의 합 구하기(1D)

https://beta.jungol.co.kr/problem/3135

 

한번 입력된 값은 변화하지 않는다는 특징 덕분에 prefix sum이 가능한 것이다.

 

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

11659번: 구간 합 구하기 4

 

 

#if 1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_N 1000000
#define LL long long
using namespace std;

LL prefix[MAX_N + 1];
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//freopen("input.txt", "r", stdin);

	int N;
	int T;
	int s, e;
	cin >> N;
	cin >> T;
	LL d;

	for (int i = 1; i <= N; i++)
	{
		cin >> d;
		prefix[i] = prefix[i - 1] + d;
	}
	
	
	for (int i = 0; i < T; i++)
	{
		cin >> s >> e;
		cout << prefix[e] - prefix[s-1]<<'\n';
	}
}

#endif

 

 

 

const 구간의 합 구하기(2D)

 

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

11658번: 구간 합 구하기 3

#if 1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int N, M;
int main(void)
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;
	vector <vector<ll>> d(N + 1, vector<ll>(N+1,0));
	for (int i = 1; i <= N; i++)
	{
		int t;
		for (int j = 1; j <= N; j++)
		{
			cin >> t;
			d[i][j] = d[i][j - 1] + d[i - 1][j] - d[i - 1][j - 1] + t;
		}
	}

	cin >> M;
	int sr, sc, er, ec;
	for (int i = 0; i < M; i++)
	{
		cin >> sr >> sc >> er >> ec;
		sr--;
		sc--;
		cout << d[er][ec] - d[sr][ec] - d[er][sc] + d[sr][sc] << '\n';
	}
	return 0;
}
#endif