[BOJ] 백준 1275번: 커피숍2

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

1275번: 커피숍2

 

구간에 대한 쿼리를 처리하는 문제입니다. 전형적인 인덱스 트리, 세그먼트 트리 문제입니다.

모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다.

 

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

const int SIZETR = 262144;
int N, Q, x, y, a, b, arr[100001], OFFSET;
ll tree[SIZETR];

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

void update(int idx, int val){
	idx += (OFFSET - 1);	
	tree[idx] = val;
	while(idx > 1){
		idx >>= 1;
		tree[idx] = tree[idx*2] + tree[idx*2+1];	
	}
}

ll query(int left, int right){
	if(left > right) swap(left, right);
	left += (OFFSET - 1);
	right += (OFFSET - 1);
	
	ll res = 0;	
	while(left <= right){
		if(left % 2 == 1) res += tree[left++];
		if(right % 2 == 0) res += tree[right--];
		left >>= 1;
		right >>= 1;	
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> Q;
	
	for(int i = 0 ; i < N; ++i){
		cin >> arr[i];
	}
	
	init();
	
	while(Q--){
		cin >> x >> y >> a >> b;
		cout << query(x, y) << '\n';
		update(a, b);
	}
}

 

인덱스 트리를 구현하는 방법은 큰 틀에서 동일합니다. 지난 포스팅에서 업로드한 [BOJ] 10868번: 최솟값, 2357번: 최솟값과 최댓값과 비교해보시면 좋을 것 같습니다. N이 최대 10만이므로 OFFSET은 최대 2^17(131,072)이 될 수 있습니다. 따라서 트리의 사이즈인 SIZETR은 이 OFFSET의 2배인 2^18(262,144)로 설정해주었습니다.

 

주의할 점으로는 문제 조건에도 명시되어 있듯이 x, y가 x > y 인 입력값이 주어질 수 있으므로 그 경우 swap 해줘야한다는 것입니다. 또한 입력되는 모든 수는 int 범위 내에 있고, 구간합은 최대 10만개의 수를 합할 수 있으므로 long long 자료형을 사용해야 합니다. 

 

시간복잡도는 매 쿼리마다 O(logN)이므로 O(QlogN)입니다.