[BOJ / 세그먼트 트리] 10999 구간 합 구하기 2

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

10999번: 구간 합 구하기 2

 

10999 구간 합 구하기 2

알고리즘 : 세그먼트 트리 / 게으른 전파(Lazy Propagation)

세그먼트 트리 문제의 정석인 문제입니다. 구간 합 구하기 1에선 세그먼트 트리만 구현해도 되었지만, 2에서는 N이 커지고 쿼리가 많아져 할때마다 모든 연산을 다 해준다면 시간초과가 나게 됩니다. 이를 방지하기 위해 게으른 전파 기법을 사용하여, 세그먼트 트리에 일정 부분을 업데이트 하기로 했다면 그 자식을 다음에 들릴 때까지 업데이트를 해주지 않고 대기하다 일괄처리를 해주는 것입니다.

이를 이용하면 시간을 절약해 TLE를 피할 수 있습니다.

 

 

 

 

< CODE >

#include <iostream>

using namespace std;

#define MAX 1000005
typedef long long int ll;

int N[MAX];
ll tree[MAX * 4];
ll lazy[MAX * 4];

void lazy_propagation(int idx, int start, int end)
{
	if (lazy[idx] != 0)
	{
		tree[idx] += lazy[idx] * (end - start + 1);
		
		if (start != end)
		{
			lazy[idx << 1] += lazy[idx];
			lazy[(idx << 1) + 1] += lazy[idx];
		}

		lazy[idx] = 0;
	}
}

ll sum(int idx, int start, int end, int left, int right)
{
	lazy_propagation(idx, start, end);

	ll ret = 0;

	if (start > right || end < left)
		return 0;
	if (left <= start && end <= right)
		return tree[idx];
	else
	{
		int mid = (start + end) / 2;

		return ret = (sum(idx * 2, start, mid, left, right) + sum(idx * 2 + 1, mid + 1, end, left, right));
	}
}

void init(int idx, int start, int end)
{
	if (start == end)
		tree[idx] = N[start];
	else
	{
		int mid = (start + end) / 2;
		init(idx << 1, start, mid);
		init((idx << 1) + 1, mid + 1, end);

		tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
	}
}

void update(int idx, int start, int end, int left, int right, ll diff)
{
	lazy_propagation(idx, start, end);

	if (start > right || end < left)
		return;
	else if (left <= start && end <= right)
	{
		tree[idx] += diff * (end - start + 1);

		if (start != end)
		{
			lazy[idx << 1] += diff;
			lazy[(idx << 1) + 1] += diff;
		}
	}
	else
	{
		int mid = (start + end) / 2;

		update(idx << 1, start, mid, left, right, diff);
		update((idx << 1) + 1, mid + 1, end, left, right, diff);

		tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
	}
}

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

	int n, m, k;

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++)
		cin >> N[i];

	init(1, 1, n);

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

		cin >> o >> a >> b;

		if (o - 1)
		{
			cout << sum(1, 1, n, a, b) << '\n';
		}
		else
		{
			cin >> c;

			update(1, 1, n, a, b, c);
		}
	}

	return 0;
}

시간 : 164ms

 

태그 : #BOJ 구간합구하기2 #10999 구간합구하기2 #백준 구간합구하기2 #세그먼트트리 #LazyPropagation