구간 합 구하기_ 백준 2042번

2020-04-02 · 배운 것 · 5분 읽기

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

2042번: 구간 합 구하기

1. 풀이 방법

이 문제는 테스트케이스도 너무 많고 중간에 수열이 계속 바뀌어서 무식하게 풀면 시간초과가 난다. 그러므로 세그먼트 트리를 만들어서 풀자.
세그먼트 트리에 대해 자세히 포스팅하고 싶지만 그림을 많이 그려야 될거같아서 다음으로 미뤄둔다.ㅋㅋ

2. 코드

#include <iostream>

using namespace std;

//node는 1부터 시작
long long init(long long* arr, long long* tree, long long node, long long start, long long end)
{
	//리프노드일때
	if (start == end)
		return tree[node] = arr[start];
	//리프노드가 아닐때
	long long mid = (start + end) / 2;
	return tree[node] = init(arr, tree, node * 2, start, mid)   \
		+ init(arr, tree, node * 2 + 1, mid + 1, end);

}

long long sum(long long* tree, long long node, long long start, long long end, long long left, long long right)
{
	//1. left, right 가 start, end를 다 포함할때 
	if (left <= start && right >= end)
		return tree[node];
	//2. left, right가 아예 무관할때
	else if (right < start || left > end)
		return 0;
	//3. 애매하게 걸쳐 있을때
	else
	{
		long long mid = (start + end) / 2;
		return sum(tree, node * 2, start, mid, left, right) \
			+ sum(tree, node * 2 + 1, mid + 1, end, left, right);
	}
}

//루트노드부터 내려오면서 다 바꾸는것이 핵심!
//인자 index는 몇번째 수가 변경할것인지, diff는 그 값과 바꿀값의 차이를 뜻함
void update(long long* tree, long long node, long long start, long long end, long long index, long long diff)
{
	if (index > end || index < start)
		return;

	tree[node] += diff;
	// 리프노드까지 도달했으면 끝
	if (start == end)
		return;

	//리프노드가 아닐시
	long long mid = (start + end) / 2;
	update(tree, node * 2, start, mid, index, diff);
	update(tree, node * 2 + 1, mid + 1, end, index, diff);
}

int main(void)
{
	int n, m, k;
	cin >> n >> m >> k;


	long long* ar = new long long[n];
	long long* tre = new long long[4 * n];

	ar[0] = 0;
	tre[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> ar[i];
	}

	init(ar, tre, 1, 1, n);

	long long a, b;
	long long c;

	for (int i = 0; i < m + k; i++)
	{
		cin >> a >> b >> c;
		//update
		if (a == 1)
		{
			long long diff = c - ar[b];
			update(tre, 1, 1, n, b, diff);
			ar[b] += diff;
		}
		//sum
		else if (a == 2)
		{
			cout << sum(tre, 1, 1, n, b, c) << '\n';
		}
	}


	return 0;
}

3. 후기

위의 코드는 예전에 공부 처음할때 만들었던 코드다.

이 글을 올리기 전에 다시 한번 짜봤는데 뭘 잘못했는지 모르지만 계속 통과를 못해서 예전 코드로 올린다. ㅠㅠ
어디가 틀린거지..