[Java] 백준 11505번 : 구간 곱 구하기

1. 문제

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

11505번: 구간 곱 구하기

 

 

 

2. 풀이 과정

 

 

- h = Math.ceil(log2(N))

- tree_size = 2^(h+1)

*h가 0부터 시작하기 때문에, h+1승 해준다.

 

1. 세그먼트 트리 생성(초기화)

public static long init(int node, int start, int end) {
    if(start==end) {
        tree[node] = arr[start];
        return tree[node];
    }
    int mid = (start+end)/2;
    tree[node] = (init(node*2, start, mid)*init(node*2+1, mid+1, end))%1_000_000_007;
    return tree[node];
}

 

2. 값 변경 시

n번째 수를 찾을 때까지 재귀 들어가고, 찾으면 return

return해서 나오면서 값 업데이트!

public static long change(int node, int start, int end, int n, int su) {//n번째 수를 su로 변경
    if(start==end && start==n) {
        tree[node]=su;
        return tree[node];
    }
    int mid = (start+end)/2;
    if(mid >= n) {
        tree[node]=(change(node*2, start, mid, n, su) * tree[node*2+1])%1_000_000_007;
    }
    else {
        tree[node]=(tree[node*2]*change(node*2+1, mid+1, end, n, su))%1_000_000_007;
    }
    return tree[node];
}

 

3. 구간 합 구하기

1) 현재 구간이 구하려는 구간(from~to)안에 들면, return

2) 구하려는 구간 밖이면 return 1

3) 구간에 걸쳐있으면, 재귀

public static long getMul(int node, int start, int end, int from, int to) {
    if(from<=start && end<=to) {
        return tree[node];
    }

    if(start > to || end < from) {//범위밖
        return 1;
    }
    else {
        int mid = (start+end)/2;
        return (getMul(node*2, start, mid, from, to)*getMul(node*2+1, mid+1, end, from, to))%1_000_000_007;
    }
}

 

 

전체 코드

---

import java.util.*;
import java.io.*;

public class Boj11505 {
	static long tree[];//segmentTree
	static long arr[];//N개의 값
	
	public static long init(int node, int start, int end) {
		if(start==end) {
			tree[node] = arr[start];
			return tree[node];
		}
		int mid = (start+end)/2;
		tree[node] = (init(node*2, start, mid)*init(node*2+1, mid+1, end))%1_000_000_007;
		return tree[node];
	}
	
	public static long change(int node, int start, int end, int n, int su) {//n번째 수를 su로 변경
		if(start==end && start==n) {
			tree[node]=su;
			return tree[node];
		}
		int mid = (start+end)/2;
		if(mid >= n) {
			tree[node]=(change(node*2, start, mid, n, su) * tree[node*2+1])%1_000_000_007;
		}
		else {
			tree[node]=(tree[node*2]*change(node*2+1, mid+1, end, n, su))%1_000_000_007;
		}
		return tree[node];
	}
	
	public static long getMul(int node, int start, int end, int from, int to) {
		if(from<=start && end<=to) {
			return tree[node];
		}
		
		if(start > to || end < from) {//범위밖
			return 1;
		}
		else {
			int mid = (start+end)/2;
			return (getMul(node*2, start, mid, from, to)*getMul(node*2+1, mid+1, end, from, to))%1_000_000_007;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); //수의 개수 1,000,000
		int M = Integer.parseInt(st.nextToken()); //변경이 일어나는 횟수 10,000
		int K = Integer.parseInt(st.nextToken()); //구간의 곱 구하는 횟수 10,000
		//1,000,000,007 로 나눈 나머지
		int h = (int) Math.ceil(Math.log(N)/Math.log(2));
		tree = new long[(int) Math.pow(2, h+1)];
		arr = new long[N+1];
		for(int i=1; i<=N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		init(1, 1, N);
		StringBuilder sb = new StringBuilder();
		for(int i=0, size=M+K; i<size; i++) {
			st = new StringTokenizer(br.readLine());
			switch(Integer.parseInt(st.nextToken())) {
			case 1://1 : b번째 수 => c로
				change(1, 1, N, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				break;
			case 2://2 : b~c까지 구간 곱
				sb.append(getMul(1, 1, N, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
				sb.append("\n");
				break;
			}
		}
		System.out.print(sb.toString());
	}
}

---