문제

구간 곱 구하기

풀이

구간의 곱을 구할때 구간의 배열이 변경될때마다 구간의 곱이 변경된다. 해당 연산을 배열의 개수만큼 구간별로 1만번 하려면 확실히 세그먼트로 밖에 풀 수 없는 문제이다.

1. 구간의 값 변경

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

구간의 값이 변경될때 update를 사용할때 인덱스의 start와 end 값이 같으면 해당 값이 바뀌어야 하는 값이므로 해당 노드를 배열의 index 값으로 설정해준다

2. 구간 곱 구하기

private static long muliply(int start, int end, int node, int left, int right) {
	if (start > end || end < left) {
    	return 1;
    }
    if (start >= left && end <= right) {
    	return tree[node];
    }
    int mid = (start + mid) / 2;
    int left = muliply(start, mid, node * 2, left, right);
    int right = muliply(mid + 1, end, node * 2 + 1, left, right);
    return left * right % 100000007;
}

전체 코드

전체 코드