알고리즘

풀이 '부모노드 = 왼쪽 자식노드 * 오른쪽 자식노드' 이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] ary; static long[] tree; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(..

풀이 구간 합 구하기에서 풀었던 방법은 '부모노드 = 왼쪽 자식노드 + 오른쪽 자식노드' 였다. 이 문제에서는 최솟값을 구할 때는 '부모노드 = Math.min(왼쪽 자식노드, 오른쪽 자식노드)' 최댓값을 구할 때는 '부모노드 = Math.max(왼쪽 자식노드, 오른쪽 자식노드)' 로 구하면 된다. + min∙max 세그먼트 트리를 초기화할 때(init 함수) 구간에서의 min∙max를 구할 때(query 함수) 전체 탐색 범위를 1~N, 0~N-1 / 구간 탐색 범위 left right를 left-1~right-1, left~right 로 설정하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..

풀이 - 세그먼트 트리 구현 https://book.acmicpc.net/ds/segment-tree 세그먼트 트리 누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다. book.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOE..