[BOJ/2042] 구간 합 구하기 (C++)

개요

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

2042번: 구간 합 구하기

세그먼트 트리 기초 문제 (G1)

풀이

• Range Sum Query를 처리하는 Segment Tree를 구현하면 된다.
• Ai의 범위가 약 ±2^63 이기 때문에 자료형 주의 !

 

코드

#include<bits/stdc++.h>	
using namespace std;
using ll = long long;

class segment_tree{
	private:
		vector<ll> tree;

	public:
		segment_tree(int N){
			int level = ceil(log2(N));
			tree.resize(pow(2, level+1));
		}
		void init(int start, int end, int node, const vector<ll> &v){
			if(start == end){
				tree[node] = v[start];
				return;
			}
			int mid = (start + end) / 2;
			init(start, mid, node*2, v);
			init(mid+1, end, node*2+1, v);
			tree[node] = tree[node*2] + tree[node*2+1];
		}
		void update(int start, int end, int node, const int &idx, const ll &val){
			if(idx < start || idx > end) return;
			if(start == end){
				tree[node] = val;
				return;
			}
			int mid = (start + end) / 2;
			update(start, mid, node*2, idx, val);
			update(mid+1, end, node*2+1, idx, val);
			tree[node] = tree[node*2] + tree[node*2+1];
		}

		ll query(int start, int end, int node, const int &left, const int &right)
		{
			if(start > right || end < left) return 0;
			if(start >= left && end <= right) return tree[node];
			int mid = (start + end) / 2;
			return query(start, mid, node*2, left, right) + query(mid+1, end, node*2+1, left, right);
		}
};

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int n, m, k;
	cin >> n >> m >> k;
	
	vector<ll> v(n+2);
	segment_tree tree(n);
	
	for(int i=1 ; i<=n; i++)
		cin >> v[i];
		
	tree.init(1, n, 1, v);
	
	ll a,b,c;
	for(int i=0; i<m+k; i++)
	{
		cin >> a >> b >> c;
		if(a==1)
			tree.update(1, n, 1, b, c);
		else if(a==2)
			cout << tree.query(1, n, 1, b, c) << "\n";
	}

}