문제

수열과 쿼리 16

풀이

배열 선언시에 자꾸 배열을 전체로 안넣어서 몇번 틀렸다. 테스트 케이스가 한개밖에 없어서 오타 찾기가 힘들었다. 이 문제 와 유사한 문제인데 범위 의 작은 값을 출력하는 부분만 다르다.
확실히 항상 그렇듯이 범위내 가장 작은 값을 구하는 부분에서 자꾸 어려워하는것 같다

private static int minIndex(int x, int y ) {
	if (arr[x] == arr[y]) {
    	return Math.mix(x,y);
    }
    return arr[x] > arr[y] ? y : x;
}

private static int getMin(int start, int end, int node, int left, int right) {
	if (left > end || start < right) {
    	return 0;
    }
    if (left <= start && right >= end) {
    	return tree[node];
    }
    int mid = (start + end) /2;
    int l = getMin(start, mid, node * 2, left, right);
    int r = getMin(mid+ 1, end, node * 2 +1 , left, right);
    return minIndex(l,r);
}

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

전체 코드

전체 코드