[자료구조] 백준 18436번: 수열과 쿼리 37 (C++)

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

18436번: 수열과 쿼리 37

이번 문제에서 포인트는 3가지라고 생각한다. (그냥 2가지 + 개인적인 1가지)

• 홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다.
• 홀수 세그 트리로 만드는 게 더 편하다.
• update를 전처리 함수를 차용해서 만들었다.

[홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다.]

처음엔 둘 다 만들어야 하나 생각했지만 하나만 만들고서 (구간 범위) - (쿼리 값)을 해주면 반대 쿼리 값이 되기 때문에 두 개의 세그 트리를 만들 필요는 없다.

else if (a == 2) {
	cout << (c - b + 1) - query(1, n, 1, b, c) << '\n';
}
else {
	cout << query(1, n, 1, b, c) << '\n';
}

[홀수 세그 트리로 만드는 게 더 편하다.]

트리 전처리 함수를 보면 알겠지만 일종의 트릭처럼 전처리 함수를 짰다. 홀수의 나머지가 1인 점을 이용하여 홀수 1개로 볼 수 있게끔하는 트릭

int sgInit(int start, int end, int node) {
	if (start == end) {
		// 홀수면 1, 짝수면 0
		// 일종의 트릭? 처럼 했다.
		return sgTree[node] = (arr[start] % 2);
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = sgInit(start, mid, node * 2) + sgInit(mid + 1, end, node * 2 + 1);
}

[update를 전처리 함수를 차용해서 만들었다.]

점점 세그 트리에 대한 감이 더 크게 잡히기 시작하지만 여전히 애매한 부분이 update였다. '말단 노드부터 해야 할지 부모 노드부터 해야 할지' 그러다가 이번 문제에서 좀 정리가 된 거 같다. 아무래도 말단 노드부터 업데이트를 해야 하는 게 맞을 거 같아서 아무 생각 없이 트리 전처리 함수처럼 짜면 되겠다는 아이디어가 나왔던 거 같다.

 

[말단 노드부터 할 때]

int update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return sgTree[node];
	if (start == end) {
		return sgTree[node] = value % 2;
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = update(start, mid, node * 2, index, value) + 
		update(mid + 1, end, node * 2 + 1, index, value);
}

[부모 노드부터 할 때, 틀린 코드이지만 그냥 느낌만]

int update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return sgTree[node];
	if (start <= index && index <= end) {
		return sgTree[node];
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = update(start, mid, node * 2, index, value) + 
		update(mid + 1, end, node * 2 + 1, index, value);
}

[AC 코드]

#include <iostream>
#define MAX (100000 + 1)
using namespace std;

int arr[MAX];
int sgTree[MAX * 4];
int n, m;

int sgInit(int start, int end, int node) {
	if (start == end) {
		// 홀수면 1, 짝수면 0
		// 일종의 트릭? 처럼 했다.
		return sgTree[node] = (arr[start] % 2);
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = sgInit(start, mid, node * 2) + sgInit(mid + 1, end, node * 2 + 1);
}

int update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return sgTree[node];
	if (start <= index && index <= end) {
		return sgTree[node];
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = update(start, mid, node * 2, index, value) + 
		update(mid + 1, end, node * 2 + 1, index, value);
}

int query(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) {
		return sgTree[node];
	}
	int mid = (start + end) / 2;
	return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sgInit(1, n, 1);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, n, 1, b, c);
			
		}
		else if (a == 2) {
			cout << (c - b + 1) - query(1, n, 1, b, c) << '\n';
		}
		else {
			cout << query(1, n, 1, b, c) << '\n';
		}
	}
	return 0;
}