c언어 14428번 수열과 쿼리 16 (백준)

#include <stdio.h>

typedef struct Node{ //최소값과, 인덱스를 담을 구조체 입니다.
   int min, index;
}Node;

Node a[100001]; //구조체로 숫자와
Node tree[400004]; //구조체로 트리를 구성합니다.

Node min(Node x, Node y) { //최소값 구하기
    if(x.min != y.min) return (x.min < y.min) ? x : y; //최솟값이 다르다면, 더 작은 구조체로
    else return (x.index < y.index) ? x : y; //최솟값이 같다면, index가 작은 걸로
}

Node init(int start, int end, int node) { //트리 초기화 하기
    if(start == end) return tree[node]= a[start];
    int mid = (start+end)/2;
    return tree[node] = min(init(start, mid, node*2), init(mid+1, end, node*2+1));
}

Node find(int start, int end, int node, int left, int right) { //구간의 최솟값 찾기
    if(start > right || end < left) { //범위가 다르면, 더이상 찾을 이유가 없다.
    	Node tmp = {1000000001, 0}; //범위보다 더 큰 수를 최솟값으로, index는 0으로 반환
    	return tmp;
	}
    if(left <= start && end <= right) return tree[node]; //범위에 속하면 그 구간의 최솟값을 반환
    int mid = (start+end) / 2;
    return min(find(start, mid, node*2, left, right), find(mid+1, end, node*2+1, left, right));
    //자식노드 들 중 더 작은 최솟값을 반환
}

void update(int start, int end, int node, int index) { //단일 요소 바꾸기
//바꿀 요소까지 내려간 다음, 값을 교체후, 올라오면서, 최솟값들을 비교하여 갱신합니다.
    if(index < start || index > end) return; //범위를 벗어남
    if(start == end) { //자식노드가 없는 경우
    	if(start == index) tree[node] = a[index]; //바꿀 요소라면 교체
    	return; 
	}
    
    int mid = (start+end)/2;
    update(start, mid, node*2, index);
    update(mid+1, end, node*2+1, index);
    tree[node] = min(tree[node*2], tree[node*2+1]); //자식노드 들 중 최솟값으로 갱신합니다.
}


int main(void) {
    int n, m;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
    	scanf("%d", &a[i].min); //요소를 입력받음
    	a[i].index = i; //인덱스를 설정함
	}
    init(1, n, 1); //트리 배열 초기화
    
    scanf("%d", &m);
    while(m--) {
        int b, c, d;
        scanf("%d %d %d", &b, &c, &d);
        if(b==1) {
        	a[c].min = d; //요소를 갱신
            update(1, n, 1, c); //트리의 최솟값들도 갱신
        }
        else {
            printf("%d\n", find(1, n, 1, c, d).index); //구간의 최솟값 출력
        }
    }
    
}

 

풀이 : segment tree

1. 요소들을 입력받습니다.

2. 세그먼트 트리를 만들되, 최솟값들로 트리를 구성해야 합니다.

3. m을 입력 받습니다.

4. 1을 입력 받으면 요소를 갱신하고, 그와 관련된 트리의 최솟값들을 갱신합니다.

4.1 재귀함수에서, 일단 교체할 요소만 포함하는 트리까지 내려간 다음, 값을 갱신 한 뒤, 올라가면서 자식노드끼리 최솟값을 비교하여 더 작은 값으로 tree 들을 갱신 합니다.

5. 2을 입력 받으면 구간의 최솟값을 출력합니다.

 

 

주의 : 이 코드는 좋지 않은 코드 입니다.

 

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

14428번: 수열과 쿼리 16