[백준/BOJ] 백준 10999번 : 구간 합 구하기 2

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

10999번: 구간 합 구하기 2

구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리를 이용해 문제를 해결했다.

 

코드

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

//구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리 이용

int n, m, k;
vector<long long> inputs;
vector<long long> sgmtt(4000000, 0);
vector<long long> lazy_check(4000000, 0); //해당 노드에서 갱신해야될 정보 저장

long long MakeSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return sgmtt[here] = inputs[range_left];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = MakeSgmtt(left_child, range_left, range_mid) + MakeSgmtt(right_child, range_mid + 1, range_right);
}

long long QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	//현재 위치에서 갱신해야 될것이 있을때
	if (lazy_check[here] != 0)
	{
		//현재 위치 갱신
		sgmtt[here] += (lazy_check[here] * (range_right - range_left + 1));

		//현재 노드가 리프노드가 아닐때, 자식 노드로 갱신 정보를 전달한다
		if (range_left != range_right)
		{
			lazy_check[left_child] += lazy_check[here];
			lazy_check[right_child] += lazy_check[here];
		}

		lazy_check[here] = 0;
	}

	if (find_right < range_left || range_right < find_left)
		return 0;

	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	return QuerySgmtt(left_child, range_left, range_mid, find_left, find_right) + QuerySgmtt(right_child, range_mid + 1, range_right, find_left, find_right);
}

long long UpdateSgmtt(int here, int range_left, int range_right, int update_left, int update_right, long long add_value)
{
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	//현재 위치에서 갱신해야 될것이 있을때
	if (lazy_check[here] != 0)
	{
		sgmtt[here] += (lazy_check[here] * (range_right - range_left + 1));

		//현재 노드가 리프노드가 아닐때, 자식 노드로 갱신 정보를 전달한다
		if (range_left != range_right)
		{
			lazy_check[left_child] += lazy_check[here];
			lazy_check[right_child] += lazy_check[here];
		}

		lazy_check[here] = 0;
	}

	//현재 범위가 업데이트 하는 범위와 상관 없을때
	if (update_right < range_left || range_right < update_left)
		return sgmtt[here];

	//현재 범위가 업데이트 하는 범위에 속할때
	if (update_left <= range_left && range_right <= update_right)
	{
		//현재 위치 갱신
		sgmtt[here] += (add_value * (range_right - range_left + 1));

		//현재 노드가 리프노드가 아닐때
		if (range_left != range_right)
		{
			//자식 노드에 갱신할 정보를 저장해 놓는다
			lazy_check[left_child] += add_value;
			lazy_check[right_child] += add_value;
		}

		return sgmtt[here];
	}

	return sgmtt[here] = UpdateSgmtt(left_child, range_left, range_mid, update_left, update_right, add_value) + UpdateSgmtt(right_child, range_mid + 1, range_right, update_left, update_right, add_value);
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

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

		inputs.push_back(input);
	}

	MakeSgmtt(0, 0, n - 1);

	for (int i = 0; i < m + k; i++)
	{
		int a, b, c;
		long long d;

		cin >> a;

		if (a == 1)
		{
			cin >> b >> c >> d;

			UpdateSgmtt(0, 0, n - 1, b - 1, c - 1, d);
		}

		else
		{
			cin >> b >> c;

			cout << QuerySgmtt(0, 0, n - 1, b - 1, c - 1) << "\n";
		}
	}

	return 0;
}