[백준 2042] 구간 합 구하기

1. 문제 

 

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

2042번: 구간 합 구하기

---

2. 풀이

 

기본적인 세그먼트 트리 문제이다. 나는 세그먼트 트리보다 인덱스 트리를 선호하므로 인덱스 트리로 설명하겠다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자!

인덱스 트리 : https://kinngife.tistory.com/32

인덱스 트리 (Binary Indexed Tree)

 

N이 최대 100만이므로 100만보다 처음으로 크거나 같아지는 2의 제곱수는 1,048,576이다. 이 값을 $OFFSET$이라고 하였을 때, 인덱스 트리를 나타내는 tree 배열은 $OFFSET$ * 2만큼의 크기가 필요하다. N개의 수를 arr 배열에 입력받고 init 함수를 통해 tree 배열을 초기화한다.

 

int OFFSET = 1048576;
vector<ll>arr(1000001);
vector<ll>tree(OFFSET * 2);

void init() {
	for (int i = 0; i < N; i++) tree[i + OFFSET] = arr[i];
	for (int i = OFFSET - 1; i > 0; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
}

 

다음 M+K 줄에 걸쳐 정수 a, b, c를 입력받는데, a가 1인 경우에는 update 함수를 통해 tree 배열을 update 하고, a가 2인 경우에는 query 함수를 통해 구간 합을 출력한다. 입력받는 정수의 범위가 long long형이므로 int형으로 선언하여 틀리는 것에 주의한다.

 

void update(ll idx, ll num) {
	idx += OFFSET;
	tree[idx] = num;
	while (idx > 1) {
		idx /= 2;
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
}
ll query(ll left, ll right) {
	ll ret = 0;
	left += OFFSET, right += OFFSET;
	while (left <= right) {
		if (left % 2 == 1) ret += tree[left++];
		if (right % 2 == 0) ret += tree[right--];
		left /= 2, right /= 2;
	}
	return ret;
}

 

---

3. 전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <climits>
#include <cmath>
#define INF INT_MAX
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int N, M, K;
int OFFSET = 1048576;
vector<ll>arr(1000001);
vector<ll>tree(OFFSET * 2);

void init() {
	for (int i = 0; i < N; i++) tree[i + OFFSET] = arr[i];
	for (int i = OFFSET - 1; i > 0; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void update(ll idx, ll num) {
	idx += OFFSET;
	tree[idx] = num;
	while (idx > 1) {
		idx /= 2;
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
}
ll query(ll left, ll right) {
	ll ret = 0;
	left += OFFSET, right += OFFSET;
	while (left <= right) {
		if (left % 2 == 1) ret += tree[left++];
		if (right % 2 == 0) ret += tree[right--];
		left /= 2, right /= 2;
	}
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];
	
	init();

	M += K;
	while (M--) {
		ll a, b, c; cin >> a >> b >> c;
		if (a == 1) update(b - 1, c);
		else cout << query(b - 1, c - 1) << "\n";
	}

	return 0;
}