개요

백준 2268: 수들의 합 7

• 입력
  첫째 줄에는 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. 세그먼트 트리를 이용하여 풀었다.

2. 주의할 점은 값 k가 범위가 10만 내라서 안심하고 int형으로 세그먼트 트리의 자료형을 정했지만, 10만을 100만번 더하면 천억이므로 int값을 넘어간다.
   long long자료형을 사용해야 한다.

전체 코드

#include<iostream>

using namespace std;
long long segmentTree[2'097'152];
int N, M, firstLeafIdx = 1;

//목표 구간 [targetL, targetR]에서의 합 리턴하는 함수, 현재 탐색 노드 nodeNum, 현재 구간 [curL, curR] 
long long ReturnSum(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (curR<targetL || curL>targetR) return 0;
	if (targetL <= curL && curR <= targetR) return segmentTree[nodeNum];

	int mid = (curL + curR) / 2;
	return ReturnSum(targetL, targetR, nodeNum * 2, curL, mid) + ReturnSum(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
}
//리프노드에서 i번째 인덱스값을 k로 바꾸는 함수
 void Mod(int i, int k) {
	int tmpIdx = firstLeafIdx + i;
	int change = k-segmentTree[tmpIdx];
	while (tmpIdx > 0) {
		segmentTree[tmpIdx] +=change;
		tmpIdx /= 2;
	}
}
 //i번째 인덱스부터 j번째 인덱스까지의 합을 구해 리턴하는 함수
void Sum(int i, int j) {
	if (i > j) swap(i, j);

	cout << ReturnSum(i, j, 1, 0, firstLeafIdx - 1)<<'\n';
}

void Input() {
	int a = 0,b=0,c=0;
	cin >> N >> M;
	//리프노드의 시작 인덱스 구하기
	while (firstLeafIdx < N)
		firstLeafIdx *= 2;

	for (int i = 0; i < M; i++) {
		cin >> a>>b>>c;
		if (a) {
			Mod(b - 1, c);
		}
		else {
			Sum(b - 1, c - 1);
		}
	}
}

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

}

문풀후생

위 접근방식에 적은 것과 같이 자료형을 간과하여 int로 적어서
틀렸었다.