(정올) 상수구간 탐색(1D), 상수구간 탐색(2D)

#if 1
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <unordered_map>
#define ll long long
#define MAX_N 1000001
using namespace std;

int N;
vector<ll> d(MAX_N);
vector<ll> p(MAX_N);
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef _WIN64	
	freopen("input.txt", "r", stdin);
#endif // _WIN64

	cin >> N;

	p(0) = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> d(i);
		p(i) = p(i - 1) + d(i);
	}
	int t;
	cin >> t;
	int a, b;
	while (t--)
	{
		cin >> a >> b;
		cout << p(b) - p(a - 1) << '\n';
	}
}
#endif

#if 1
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <unordered_map>
#define ll long long
#define MAX_N 1001
using namespace std;


int N;
vector<vector<ll>> d(MAX_N, vector<ll>(MAX_N));
vector<vector<ll>> p(MAX_N, vector<ll>(MAX_N));
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef _WIN64
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> d(i)(j);
			p(i)(j) = p(i - 1)(j) + p(i)(j - 1) - p(i - 1)(j - 1) + d(i)(j);
		}
	}

	int t;
	cin >> t;
	int sr, sc, er, ec;
	while (t--)
	{
		cin >> sr >> sc >> er >> ec;
		cout << p(er)(ec) - p(er)(sc - 1) - p(sr - 1)(ec) + p(sr - 1)(sc - 1)<<'\n';
	}
}
#endif