백준 2268: 수들의 합 7

문제 요약

N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.

Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i] = k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

어떠한 구간 사이에서 일관성있는 연산과 수정을 반복하는 특징을 갖고 있으므로 세그먼트 트리 자료 구조로 풀었다.

다른 세그먼트 트리문제와 다른 점은 초기화가 불필요한 점이다. 이미 배열이 0으로 초기화 되어있으므로 따로 구축이 불필요하다.

입력의 첫 인자에 따라 행하는 함수가 다르게 하였다. 0이면 구간 합을, 1이면 수정하는 연산을 해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

long long seg[4000000];
int n;

long long update(int l, int r, int loc, int idx, int val)
{
	if (idx < l || idx > r) return seg[loc];
	if (l == r) {
		if (l == idx) seg[loc] = val;
		return seg[loc];
	}
	int mid = (l + r) / 2;

	seg[loc] = update(l, mid, loc * 2 + 1, idx, val) + update(mid + 1, r, loc * 2 + 2, idx, val);
	return seg[loc];
}

long long sum(int L, int R, int l, int r, int idx)
{
	if (l > R || r < L) return 0;
	if (L <= l && R >= r) return seg[idx];
	int mid = (l + r) / 2;
	return sum(L, R, l, mid, idx * 2 + 1) + sum(L, R, mid + 1, r, idx * 2 + 2);
}

int main()
{
	int m, in1, in2, in3;
	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &in1, &in2, &in3);
		in2--;
		if (in1)
			update(0, n - 1, 0, in2, in3);
		else {
			in3--;
			if (in2 > in3) swap(in2, in3);
			printf("%lld\n", sum(in2, in3, 0, n - 1, 0));
		}
	}

	return 0;
}