c언어 18436번 수열과 쿼리 37 (백준)

#include <stdio.h>

int arr[100001]; //요소를 담는 배열
int tree[400004]; //트리를 구성하는 배열

int init(int s, int e, int node) { //트리를 초기화 합니다.
	if(s==e) return tree[node] = arr[s];
	int mid = (s+e)/2;
	return tree[node] = init(s, mid, node*2) + init(mid+1, e, node*2+1);
}

int find(int s, int e, int node, int l, int r) { //트리에서 구간의 홀수의 개수를 구합니다.
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int mid = (s+e)/2;
	return find(s, mid, node*2, l, r) + find(mid+1, e, node*2+1, l, r);
}

void update(int s, int e, int node, int index, int dif) { //트리의 요소를 갱신합니다.
	if(s > index || e < index) return;
	tree[node] += dif;
	if(s==e) return;
	int mid = (s+e)/2;
	update(s, mid, node*2, index, dif);
	update(mid+1, e, node*2+1, index, dif);
	return;
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) { //요소 입력받기
		scanf("%d", &arr[i]);
		arr[i] &= 1;
	}
	
	init(1, n, 1); //트리 초기화
	
	scanf("%d", &m);
	while(m--) { 
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if(a == 1) { //1일 경우 요소를 갱신합니다.
			int tmp = (c&1)-arr[b];
			update(1, n, 1, b, tmp);
			arr[b] = c&1;
		}
		else  { //2일 경우 짝수의 개수를, 3일 경우엔 홀수의 개수를 구한 뒤 출력합니다.
			if(a == 2) printf("%d\n", (c-b+1)-find(1, n, 1, b, c)); //짝수는 범위의 크기 - 그 범위중 홀수 인 것 을 빼면 구할 수 있습니다.
			else printf("%d\n", find(1, n, 1, b, c));
		}
	}
}

 

풀이 : segment tree

 

1. 배열을 만듭니다.

2. n개의 숫자들을 받습니다. 이 과정에서, 홀수는 1로 짝수는 0으로 저장합니다.

3. 트리를 초기화 합니다. 트리에서는 홀수의 개수의 구간합을 저장합니다.

4. 1을 입력 받으면, 요소를 하나 바꾸며, 이와 관련된 트리도 갱신한다.

5. 2을 입력 받으면, 구간에 존재하는 홀수의 개수를 구한다음, 구간의 크기에 홀수의 개수를 빼면 짝수의 개수를 구할 수 있으며, 이를 출력하면 됩니다.

6. 3을 입력 받으면, 구간에 존재하는 홀수의 개수를 구한다음, 출력합니다.

 

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

18436번: 수열과 쿼리 37