[백준/BOJ] 백준 2042번 : 구간 합 구하기

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

세그먼트 트리의 쿼리와 업데이트를 이용해서 문제를 해결했다. 세그먼트 트리에 사용하는 각 구간의 합을 저장하는 배열을 넉넉하게 4*n으로 했다.

 

코드

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

int n, m, k;
vector<long long> range_sum; //세그먼트 트리
vector<long long> input_data;

//세그먼트 트리 만들기
long long Make_range_sum(int node, int left, int right)
{
	if (left == right)
		return range_sum[node] = input_data[left];

	int mid = (left + right) / 2;
	int left_child = node * 2 + 1;
	int right_child = node * 2 + 2;

	return range_sum[node] = Make_range_sum(left_child, left, mid) + Make_range_sum(right_child, mid + 1, right);
}

//세그먼트 트리 쿼리
long long Query(int node, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 0;

	if (find_left <= range_left && range_right <= find_right)
		return range_sum[node];

	int mid = (range_left + range_right) / 2;
	int left_child = node * 2 + 1;
	int right_child = node * 2 + 2;

	return Query(left_child, range_left, mid, find_left, find_right) + Query(right_child, mid + 1, range_right, find_left, find_right);
}

//세그먼트 트리 업데이트
long long Update(int node, int range_left, int range_right, int index, long long update_value)
{
	if (range_left == range_right && range_left == index)
		return range_sum[node] = update_value;

	if (index < range_left || range_right < index)
		return range_sum[node];

	int mid = (range_left + range_right) / 2;
	int left_child = node * 2 + 1;
	int right_child = node * 2 + 2;

	return range_sum[node] = Update(left_child, range_left, mid, index, update_value) + Update(right_child, mid + 1, range_right, index, update_value);
}

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

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		int input;

		cin >> input;

		input_data.push_back(input);
	}

	range_sum.resize(n * 4);//세그먼트 트리에 사용하는 각 구간의합을 저장하는 배열을 넉넉하게 4*n으로 한다

	Make_range_sum(0, 0, n - 1); //세크먼트 트리 만들기

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

		cin >> a >> b >> c;

		if (a == 1)
		{
			Update(0, 0, n - 1, b - 1, c);
		}

		else if (a == 2)
		{
			cout << Query(0, 0, n - 1, b - 1, c - 1) << "\n";
		}
	}

	return 0;
}