[백준] 수들의 합 (2268번)

문제

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 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

입력

첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 나타내며, 0일 경우에는 Sum 함수를, 1일 경우에는 Modify 함수를 나타낸다. 다음 두 수는 각 함수의 인자 (i, j)나 (i, k)를 나타낸다. 처음에는 A[1]=A[2]=…A[N]=0이다. Modify인 경우에 1 ≤ k ≤ 100,000 이다.

출력

Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값을 출력한다.

예제 입력 1 복사

3 5 0 1 3 1 1 2 1 2 3 0 2 3 0 1 3

예제 출력 1 복사

0 3 5

---

세그먼트 트리 문제다.

구간의 합을 출력하거나, 특정 위치의 값을 수정해주는 작업을 해야한다.

구간합은 int 범위를 넘을 수 있으므로 long long 자료형으로 해줘야 한다.

 

문제에서 틀린 부분은 구간합을 구할 때 구간 인덱스가 순서대로 나오지 않고 뒤집어서 나올 수 있다.

예를들어 2 ~ 4번째 구간의 합을 구하려 할 때 0, 2, 4 로 주어지는 게 아닌 0, 4, 2로 입력이 들어올 수 있다.

이런 경우에 swap만 해주면 평범한 세그먼트 트리 문제와 같다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%88%98%EB%93%A4%EC%9D%98%20%ED%95%A9%20(2268%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
int N, M;
vector<long long> range;
int p[1000001];

long long init(int left, int right, int node) {
	if (left == right) return range[node] = p[left];
	int mid = (left + right) / 2;
	return range[node] = init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
}

long long query(int left, int right, int node, int nodeLeft, int nodeRight) {
	if (left <= nodeLeft && nodeRight <= right) return range[node];
	if (right < nodeLeft || nodeRight < left) return 0;
	int mid = (nodeLeft + nodeRight) / 2;
	return query(left, right, node * 2, nodeLeft, mid) + query(left, right, node * 2 + 1, mid + 1, nodeRight);
}

void update(int idx, int value, int node, int nodeLeft, int nodeRight){
	if (idx < nodeLeft || nodeRight < idx) return;
	if (nodeLeft == nodeRight) {
		p[idx-1] = range[node] = value;
		return;
	}
	int mid = (nodeLeft + nodeRight) / 2;
	update(idx, value, node * 2, nodeLeft, mid);
	update(idx, value, node * 2 + 1, mid + 1, nodeRight);
	range[node] = range[node * 2] + range[node * 2 + 1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	range.resize(N * 4);
	init(0, N - 1, 1);
	for (int a, b, c, i = 0; i < M; i++) {
		cin >> a >> b >> c;
		if (a == 0) {
			if (b > c) swap(b, c);
			cout << query(b - 1, c - 1, 1, 0, N - 1) << "\n";
		}
		else {
			update(b - 1, c, 1, 0, N - 1);
		}
	}
}