[백준/BOJ] 백준 11658번 : 구간 합 구하기 3

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

11658번: 구간 합 구하기 3

2차원 세그먼트 트리를 이용해서 문제를 해결했다.

 

코드

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

//2차원 세그먼트를 이용해서 문제를 해결

int n, m;
vector<vector<int>> board(1024, vector<int>(1024, 0));
vector<vector<int>> sgmtt(1024 * 2, vector<int>(1024 * 2, 0));

void MakeSgmtt()
{
	//큰 세그먼트 트리의 리프노드안의 세그먼트의 리프노드 채우기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			sgmtt[i + n][j + n] = board[i][j];
		}
	}

	//큰 세그먼트 트리의 리프노드안의 세그먼트 트리 채우기
	for (int i = n; i < 2 * n; i++)
		for (int j = n - 1; j >= 1; j--)
		{
			sgmtt[i][j] = sgmtt[i][j * 2] + sgmtt[i][j * 2 + 1];
		}

	//큰 세그먼트 트리의 리프노드가 아닌 노드안의 세그먼트 트리 채우기
	for (int j = 1; j < 2 * n; j++)
		for (int i = n - 1; i >= 1; i--)
		{
			sgmtt[i][j] = sgmtt[i * 2][j] + sgmtt[i * 2 + 1][j];
		}
}

void UpdateSgmtt(int x, int y, int value)
{
	sgmtt[x + n][y + n] = value;

	//큰 세그먼트 트리의 리프노드안의 세그먼트 트리 업데이트
	for (int j = (y + n) / 2; j >= 1; j = j / 2)
	{
		sgmtt[x + n][j] = sgmtt[x + n][j * 2] + sgmtt[x + n][j * 2 + 1];
	}

	//큰 세그먼트 트리의 리프노드가 아닌 노드의 세그먼트 트리 업데이트
	for (int i = (x + n) / 2; i >= 1; i = i / 2)
	{
		sgmtt[i][y + n] = sgmtt[i * 2][y + n] + sgmtt[i * 2 + 1][y + n];

		for (int j = (y + n) / 2; j >= 1; j = j / 2)
		{
			sgmtt[i][j] = sgmtt[i][j * 2] + sgmtt[i][j * 2 + 1];
		}
	}

}

int QuerySgmtt2(int x, int y1, int y2)
{
	int ret = 0;

	y1 = y1 + n;
	y2 = y2 + n;

	while (y1 < y2)
	{
		if (y1 % 2 == 1)
		{
			ret += sgmtt[x][y1];
			y1++;
		}

		if (y2 % 2 == 0)
		{
			ret += sgmtt[x][y2];
			y2--;
		}

		//부모 노드로 올라가기
		y1 /= 2;
		y2 /= 2;
	}

	if (y1 == y2)
		ret += sgmtt[x][y1];

	return ret;
}

int QuerySgmtt1(int x1, int y1, int x2, int y2)
{
	int ret = 0;

	x1 = x1 + n;
	x2 = x2 + n;

	while (x1 < x2)
	{
		if (x1 % 2 == 1)
		{
			ret += QuerySgmtt2(x1, y1, y2);
			x1++;
		}

		if (x2 % 2 == 0)
		{
			ret += QuerySgmtt2(x2, y1, y2);
			x2--;
		}

		//부모노드로 올라가기
		x1 /= 2;
		x2 /= 2;
	}

	if (x1 == x2)
		ret += QuerySgmtt2(x1, y1, y2);

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	MakeSgmtt();

	for (int i = 0; i < m; i++)
	{
		int w;
		int x, y, c;
		int x1, y1, x2, y2;

		cin >> w;

		if (w == 0)
		{
			cin >> x >> y >> c;
			x--;
			y--;
			UpdateSgmtt(x, y, c);
		}

		else
		{
			cin >> x1 >> y1 >> x2 >> y2;

			x1--;
			y1--;
			x2--;
			y2--;
			int min_x = min(x1, x2);
			int min_y = min(y1, y2);
			int max_x = max(x1, x2);
			int max_y = max(y1, y2);

			cout << QuerySgmtt1(min_x, min_y, max_x, max_y) << "\n";
		}
	}

	return 0;
}