백준 2042번 구간 합 구하기

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

 

 

세그멘트 트리 

www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

 

1. i ~ j 범위의 합을 구하는 경우

2. 도중 어느 인덱스에서 갱신이 일어나는 경우

그냥 풀면 O(NM)

세그멘테이션 트리

 

1. N개의 인덱스에 대해 인덱스 범위를 담당할 노드를 결정

1번 노드는 1~N을 담당

2번 노드는 1~N/2 , 3번노드는 N/2+1~N 담당.

이런식으로 트리구조로 내려감

리프 노드는 해당 인덱스가 갖는 num값을 그대로 저장.

리프 노드가 아니면 자신이 담당하는 모든 인덱스가 갖는 num의 합을 저장.

 

update는 어떤 노드에 있어서 자신이 담당하는 인덱스 중 수정하고자 하는 인덱스가 속하면

자신이 저장한 값을 수정하면 됨.

 

sum은 가령 자신이 4~M을 담당하는데 합의 범위를 원하는 것이 4~M이라면 그대로 자신이 저장한 값 반환.

하지만 1~3 혹은 M+1 ~ N은 자신이 줄게 없으므로 0

또한 5 ~ M+1과 같이 걸치는 경우 쪼개서 처리 저 영역안에 속하는 범위의 노드가 저장한 값 반환하도록 분리.

#include<iostream>

using namespace std;


int N, M, K;
long long num[1000001];
long long tree[3000001];

long long init(int n, int s, int e)
{
	if (s == e)
	{
		tree[n] = num[s];
		return tree[n];
	}
	int m = (s + e) / 2;
	tree[n] = init(n * 2, s, m) + init(n * 2 + 1, m + 1, e);
    return tree[n]
}

void update(int n, int s, int e, int t, int diff)
{
	if (s <= t && t <= e)
	{
		tree[n] += diff;
	}
	else
	{
		return;
	}

	if (s == e)
	{
		//만약 s == e면 더 이상 분리 필요 x 위에서 처리 끝남
		return;
	}
	int mid = (s + e) / 2;
	update(n * 2, s, mid, t, diff);
	update(n * 2 + 1, mid + 1, e, t, diff);
}

long long sum(int l, int r, int n, int s, int e)
{
	//출력 범주가 해당 노드를 포함
	if (l <= s && e <= r)
	{
		return tree[n];
	}
	//아예 벗어남
	if (s > r || e < l)
	{
		return 0;
	}
	//어중간하게 겹침 
	int mid = (s + e) / 2;
	return sum(l, r, n * 2, s, mid) + sum(l, r, n * 2 + 1, mid + 1, e);
}

int main()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
	}
	init(1, 1, N);
	for (int i = 0; i < M + K; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1)
		{
			int diff = c - num[b];
			num[b] = c;
			update(1, 1, N, b, diff);
		}
		else
		{
			cout << sum(b, c, 1, 1, N) << endl;
		}
			
	}
	
}