[백준 2042] 구간 합 구하기

문제 링크 => 2042번: 구간 합 구하기 (acmicpc.net)

2042번: 구간 합 구하기

---

세그먼트 트리를 이용한 구간 합 구하기 문제이다.

 

이 문제에서 쿼리 2개를 통해 다음과 같은 operation 을 한다.

 

1. 배열의 index = b 를 update 하기

이부분은 1차원 배열 arr에 대하여 arr[index] = c 로 O(1) 만에 변경이 가능하지만 기존에 만들어둔 세그먼트 트리를 활용하지 못한다.

다른 방법을 밑에서 설명하고자 한다.

 

2. 구간 [b, c] 에서의 합을 출력하기

세그먼트 트리를 통해 구간합을 구하여 출력하도록 한다.

 

그렇다면 update 를 할 때, 기존의 세그먼트 트리를 어떻게 update 할지에 따라 시간초과가 나올 수 있거나 안나올 수 있다.

 

세그먼트 트리를 update 하는 방법은 2가지 방법이 존재한다.

 

(1) 배열 arr의 값을 변경하고 다시 세그먼트 트리를 형성하는 방법

       => 시간복잡도 O(NlogN) 으로써 딱 봐도 시간초과가 나보인다. (참고로 이렇게 해서 시간초과됨)

 

(2) 변경될 index에 대하여 index를 포함하는 [left, right] 부분만 최신화하는 방법

      => O(logN) 만에 left = right = index 인 부분부터 [1, N] 까지 부모노드를 오르면서 값을 변경이 가능하다.

 

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, K;
ll arr[1000001];
ll segTree[2000001];

void build_Segtree(int idx, int left, int right) {
	if (left == right) {
		segTree[idx] = arr[left];
		return;
	}
	int mid = (left + right) / 2;
	build_Segtree(idx * 2, left, mid);
	build_Segtree(idx * 2 + 1, mid + 1, right);
	segTree[idx] = segTree[idx * 2] + segTree[idx * 2 + 1];
}

void update_Segtree(int idx, int left, int right, int update_idx, ll val) {
	if (update_idx < left || update_idx > right) return;
	if (update_idx == left && update_idx == right) {
		segTree[idx] = val;
		return;
	}
	int mid = (left + right) / 2;
	update_Segtree(idx * 2, left, mid, update_idx, val);
	update_Segtree(idx * 2 + 1, mid + 1, right, update_idx, val);
	segTree[idx] = segTree[idx * 2] + segTree[idx * 2 + 1];
}

ll query(int idx, int left, int right, int query_Left, int query_Right) {
	if (left > query_Right || right < query_Left) return 0;
	if (left >= query_Left && right <= query_Right) return segTree[idx];
	int mid = (left + right) / 2;
	return query(idx * 2, left, mid, query_Left, query_Right) +
		query(idx * 2 + 1, mid + 1, right, query_Left, query_Right);
}

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

	build_Segtree(1, 1, N);

	for (int i = 0; i < M + K; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update_Segtree(1, 1, N, b, c);
		}
		else if (a == 2) {
			cout << query(1, 1, N, b, c) << endl;
		}
	}

	return 0;
}