문제

수열과 쿼리 15

풀이

세그먼트 계속 풀수록 어렵네, 이 문제에서 주어지는 수열이 계속 변경되는데 트리에서 가장 상위에 있는 배열이 가장 작은 배열의 인덱스가 될것이므로 범위 중 가장 작은 값을 따로 찾을 필요가 없이 tree[1] 을 출력하게 되면 된다

1. 가장 작은 값의 배열의 인덱스를 출력한다

private static int minIndex(int x, int y) {
	if (arr[x] == arr[y]) { // 값이 같은 경우 인덱스가 작은 값을 출력
    	return Math.min(x,y);
    } else { // 값이 다른 경우 작은 값을 출력한다
    	arr[x] < arr[y] ? x : y;
    }
}

2. 새그먼트 트리를 초기화

private static void init(int start, int end, int node) {
	if (start == end) { // 값이 같으면 현재 인덱스를 입력
    	tree[node] = start;
        return;
    }
    int mid = (start + end ) / 2;
    init(start, mid, node * 2);
    init(min + 1, end, node * 2+1);
    tree[node] = minIndex(tree[node * 2], tree[node * 2+ 1]);
}

3. 세그먼트 트리를 수정

private static void update(int start, int end, int node, int index) {
	if (start > index || end < index) {
    	return;
    }
    if (start == end) {
    	tree[node] = index;
        return
    }
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index);
    update(mid, node * 2 + 1, index);
    tree[node] = minIndex(tree[node * 2], tree[node * 2 + 1]);
}

아 그리고 검색하다가 알게된 코드인데, 우선순위 큐로만 간단하게 풀수 있다
나중에 이 풀이도 추가 하면 좋을것같다

전체 코드

전체 코드