728x90
const 구간의 합 구하기(1D)
https://beta.jungol.co.kr/problem/3135
한번 입력된 값은 변화하지 않는다는 특징 덕분에 prefix sum이 가능한 것이다.
https://www.acmicpc.net/problem/11659
#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
#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
728x90