[BeakJoon 2042] 구간 합 구하기

안녕하세요. 이번 포스팅에서는 BeakJoon 2042 구간 합 구하기 문제를 풀어보도록 하겠습니다.

 

문제는

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

2042번: 구간 합 구하기

 

위 링크에서 확인하실 수 있습니다.

 

우선 이 문제는 구간 합 구하기 문제이긴 한데, 동적으로 계속 배열 값이 변경되기 때문에 이를 일일이 변경할 수가 없습니다.

 

https://chanho0912.tistory.com/29?category=871243 

[C++/Algorithm] 투 포인터, 구간 합 이해하기

 

원소 값의 변경이 없는 문제의 경우 위 알고리즘으로 해결하면 되지만, 만약 위 알고리즘처럼 구간합을 구해놓았다 치면,

 

값 하나가 바뀔때마다 그 값의 인덱스부터 끝 인덱스까지 값을 모두 update 해주어야 합니다. 이는 O(N^2)의 시간 복잡도를 갖게 되고, 문제의 제한이 1000000을 고려하였을 때 당연히 사용할 수 없어집니다.

 

따라서 저희는 update를 N보다 적은 횟수로 실행하는 알고리즘을 찾아야 하는데, 그 과정에서 펜윅 트리라는 자료구조를 사용하여 문제를 해결하시면 됩니다.

 

펜윅 트리를 이해하기 위해서 잠시 아래의 설명을 보시면,

 

9라는 숫자를 이진수로 나타내어 보겠습니다.

00000000 00000000 00000000 00001001

 

이번에는 -9라는 숫자를 이진수로 나타내어 보겠습니다.

11111111 11111111 11111111 11110111

 

여기서 9 & -9연산을 취하게 되면

00000000 00000000 00000000 00000001 이 나오게 되고, 9의 마지막 0이 아닌 비트는 1이라는 사실을 알게 됩니다.

즉 어떤 수 NUM의 마지막 0이 아닌 비트를 알기 위해 NUM & -NUM 연산을 해주면 된다는 사실을 알 수 있습니다. 

 

위 방식을 적용하면

0 -> 0

1 -> 1

2 -> 2

3 -> 1

4 -> 4

5 -> 1 

6 -> 2

7 -> 1

8 -> 8

 

의 값이 나오게 됩니다. 

 

이를 트리 구조에 적용해보면

 

출처 : 동빈 나 YOUTUBE 자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복

(출처 링크) 

 

0이 아닌 마지막 비트 수 = 가지고 있는 값의 개수

 

위와 같은 형태로 나타낼 수 있습니다. 예를 들면 0이 아닌 마지막 비트가 16인 수는 1~16까지의 구간의 합을 갖고 있겠다 라는 뜻입니다.

 

7의 경우 0이 아닌 마지막 비트가 1입니다. 이 경우 7 자기 자신의 값만 가지고 있다고 생각하시면 됩니다.

 

 

자 그러면, 문제의 예시처럼 3번 인덱스의 값이 변경되었다고 생각해보면, 이 tree 중 업데이트가 수행되어야 하는 노드는 몇 가지가 있을까요?

 

3,

1~4, 

1~8,

1~16

 

이렇게 총 네 개의 노드에 대해 update를 실행해주시면 됩니다. 이렇게 되면, 모든 update에 대해 logN의 시간 복잡도로 수행할 수 있고 이는 문제의 제한에 맞습니다.

 

 

<소스 코드>

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

int n, m, k;
ll arr[1000004], tree[1000004];

void update(ll idx, ll diff) {	
	while(idx <= n) {
		tree[idx] += diff;	
		idx += (idx&(-idx));
	}
}
ll sum(ll node) {
	ll ret = 0;
	while(node >= 1) {
		ret += tree[node];
		node -= (node & (-node));
	}
	return ret;
}
ll query(ll start, ll end) {
	ll ret = sum(end) - sum(start-1);
	return ret;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m >> k;
	
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		update(i, arr[i]);	
	}
	
	for(int i = 1; i <= m+k; i++) {
		ll a, b, c; cin >> a >> b >> c;
		if(a==1) {
			update(b, c-arr[b]);
			arr[b]=c;	
		}
		else cout << query(b, c) << "\n";
	}
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.