[BOJ 2042 | C++] 구간 합 구하기 :: 세그먼트 트리

• 문제 링크 : 2042번: 구간 합 구하기
• 문제 태그 : 자료 구조, 세그먼트 트리

 

풀이

비재귀 세그먼트 트리를 이용해서 풀었습니다. 

 

코드에서 template 자료형 추론(CTAD)을 이용하여 벡터를 간결하게 선언했습니다.

• 참고 자료 : [TIP] 다차원 vector 선언 팁 : 네이버 블로그
• 공식 문서 : Class template argument deduction (CTAD) (since C++17) - cppreference.com

#include <iostream>
#include <vector>

using namespace std;

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

	int n, m, k;
	cin >> n >> m >> k;

	vector v(n, 0LL);  
;	for (int i = 0;i < n;i++) cin >> v[i];

	int sz = 1;
	while (sz < n)	sz *= 2;
	vector tree(sz * 2, 0LL);

	auto init = [&] {
		for (int i = 0; i < n;i++) tree[i + sz] = v[i];
		for (int i = sz - 1;i >= 1;i--) {
			tree[i] = tree[2 * i] + tree[2 * i + 1];
		}
	};
	init();

	auto update = [&](int i, long long x) {
		i += sz;
		tree[i] = x;
		while (i > 1) {
			i /= 2;
			tree[i] = tree[2 * i] + tree[2 * i + 1];
		}
	};
	
	auto query = [&](int l, int r) {
		l += sz;
		r += sz;
		long long ans = 0;

		while (l <= r) {
			if (l % 2 == 1) {
				ans += tree[l];
				l++;
			}
			if (r % 2 == 0) {
				ans += tree[r];
				r--;
			}
			l /= 2;
			r /= 2;
		}
		return ans;
	};

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

		if (a == 1) {
			// Point update query
			update(b - 1, c);
		}
		if (a == 2) {
			// print
			cout << query(b - 1, c - 1) << '\n';
		}
	}
}