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

Segment Tree 공부하기

겉보기에는 구간합을 구하는 간단한 문제처럼보이지만

Segment Tree 자료구조를 이해해야 풀 수 있는 문제입니다.

하단 링크에 설명이 잘 되어 있습니다.

https://www.acmicpc.net/blog/view/9

하단의 영상은 제가 올린 건 아니고

유튜브에 개발자영맨님이 만든 Segment Tree 강의인데

설명이 잘 되어 있어서 같이 올려봅니다.

https://www.youtube.com/watch?v=075fcq7oCC8 

https://www.youtube.com/watch?v=ahFB9eCnI6c 

문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int n, m, k;
long long arr[1000003];

struct SegmentTree {
	int N;
	vector<long long> tree;

	long long merge(long long left, long long right) {
		return left + right;
	}

	long long buildRec(int node, int nodeLeft, int nodeRight) {
		if (nodeLeft == nodeRight) {
			return tree[node] = arr[nodeLeft];
		}

		int mid = (nodeLeft + nodeRight) / 2;

		long long LeftVal = buildRec(2 * node, nodeLeft, mid);
		long long RightVal = buildRec(2 * node + 1, mid + 1, nodeRight);

		return tree[node] = merge(LeftVal, RightVal);
	}

	void init(int Size) {
		N = Size;
		tree.resize(N * 4);
		buildRec(1, 0, N - 1);
	}

	long long queryRec(int left, int right, int node, int nodeLeft, int nodeRight) {
		// 노드 구간이 구하는 구간 밖일 경우 0 리턴
		if (nodeRight < left || right < nodeLeft) {
			return 0;
		}

		if (left <= nodeLeft && nodeRight <= right) {
			return tree[node];
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = queryRec(left, right, 2 * node, nodeLeft, mid);
		long long rightVal = queryRec(left, right, 2 * node + 1, mid + 1, nodeRight);

		return merge(leftVal, rightVal);
	}


	long long query(int left, int right) {
		return queryRec(left, right, 1, 0, N - 1);
	}

	long long updateRec(int index, long long newValue, int node, int nodeLeft, int nodeRight) {
		if (nodeRight < index || index < nodeLeft) return tree[node];
		
		if (nodeLeft == nodeRight) {
			return tree[node] = newValue;
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = updateRec(index, newValue, 2 * node, nodeLeft, mid);
		long long rightVal = updateRec(index, newValue, 2 * node + 1, mid + 1, nodeRight);


		return tree[node] = merge(leftVal, rightVal);
	}


	void update(int index, long long newValue) {
		updateRec(index, newValue, 1, 0, N - 1);
	}

};


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

	cin >> n >> m >> k;

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

	SegmentTree st;
	st.init(n);

	for (int i = n + 2; i <= n + m + k + 1; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;

		if (a == 2) {
			cout << st.query(b - 1, c - 1) << '\n';
		}
		else {
			st.update(b - 1, c);
		}
	}

	
	return 0;
}

백준 2042 반례

5 1 1
1
2
3
4
5
1 2 300000000000
2 2 5

answer: 300000000012

a, b, c 를 입력 받을 때 c를 long long 형으로 입력받아야합니다.

업데이트를 해주는 과정에서도 long long 자료형을 유지해 업데이트를 진행해야합니다.