[백준] 11505번_구간 곱 구하기

1. 문제

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

 

2. 코드

python

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())
treeHeight = 0
length = N
MOD = 1000000007

while length != 0:
    length //= 2
    treeHeight += 1

treeSize = pow(2, treeHeight+1)
leftNodeStartIndex = treeSize // 2 - 1
tree = [1] * (treeSize + 1)

for i in range(leftNodeStartIndex + 1, leftNodeStartIndex + N + 1):
    tree[i] = int(input())

def setTree(i):
    while i != 1:
        tree[i//2] = tree[i//2] * tree[i] % MOD
        i -= 1

setTree(treeSize - 1)

def changeVal(index, value):
    tree[index] = value
    while index > 1:
        index = index // 2
        tree[index] = tree[index * 2] % MOD * tree[index * 2 + 1] % MOD

def getMul(s, e):
    partMul = 1
    while s <= e:
        if s % 2 == 1:
            partMul = partMul * tree[s] % MOD
            s += 1
        if e % 2 == 0:
            partMul = partMul * tree[e] % MOD
            e -= 1
        s = s // 2
        e = e // 2
    return partMul

for _ in range(M+K):
    q, s, e = map(int, input().split())
    if q == 1:
        changeVal(leftNodeStartIndex + s, e)
    elif q == 2:
        s = s + leftNodeStartIndex
        e = e + leftNodeStartIndex
        print(getMul(s, e))

풀이

1. N - 수의 개수, M - 변경이 일어나는 개수, K - 구간 합을 구하는 개수
2. treeHeight - 트리의 높이, length - 리프 노드 개수
3. 트리 높이 구하기
4. leftNodeStartIndex 구하기 → treeSize /2 - 1( 리프 노드 시작 인덱스)
5. tree - 인덱스 트리 저장
6. tree 리스트의 리프 노드 영역에 데이터 입력
7. 함수 setTree(index) → 인덱스 트리 생성 함수
   1. while index가 루트가 아닐때까지
      1. 부모 노드(index / 2)에 현재 index의 트리값 곱하고 나머지 연산 후 저장
      2. index 1개 감소
8. setTree(트리의 크기) 함수 호출
9. 함수 changVal(시작 index, 변경값) → 값 변경 함수
   1. 현재 index위치에 신규 변경 값 저장
   2. while 시작 index > 1
      1. 시작 index = 시작 index / 2
      2. 부모 노드에 두 자식 노드값을 곱하고 나머지 연산 후 저장
10. 함수 getMul(시작 index, 종료 index) → 구간 합 계산 함수
    1. while 시작 index와 종료 index가 교차 될 때 까지
       1. if 시작 index % 2 == 1:
          1. 해당 노드의 값을 구간 곱 변수에 곱하고 나머지 연산 후 저장
          2. 시작 index 증가
       2. if 종료 index % 2 == 0:
          1. 해당 노드의 값을 구간 곱 변수에 곱하고 나머지 연산 후 저장
          2. 종료 index 감소
    2. 시작 index = 시작 index / 2
    3. 종료 index = 종료 index / 2
11. for M+K만큼 반복
    1. q - 질의 유형, s - 시작 index, e - 변경값 or 종료 index
    2. q 가 1일때 → changVal(tree에서 시작 index, e)
    3. q 가 2일때 → getMul(tree에서 시작 index, tree에서 종료 index)

 

Java

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

public class Main {
    static long[] tree;
    static int MOD;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); 
        int M = Integer.parseInt(st.nextToken()); 
        int K = Integer.parseInt(st.nextToken()); 
        int treeHeight = 0;
        int lenght = N;
        while (lenght != 0) {
            lenght /= 2;
            treeHeight++;
        }
        int treeSize = (int) Math.pow(2, treeHeight + 1);
        int leftNodeStartIndex = treeSize / 2 - 1;
        MOD = 1000000007;
        tree = new long[treeSize + 1];
        for (int i = 0; i < tree.length; i++) {   //초기 값을 곱셈이기 때문에 1로 설정
            tree[i] = 1;
        }
        for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
            tree[i] = Long.parseLong(br.readLine()); 
        }
        setTree(treeSize - 1); // tree 만들기
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            long a = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            long e = Long.parseLong(st.nextToken());
            if (a == 1) { // 변경
                changeVal(leftNodeStartIndex + s, e);
            } else if (a == 2) { // 구간 곱
                s = s + leftNodeStartIndex;
                e = e + leftNodeStartIndex;
                System.out.println(getMul(s, (int) e));
            } else {
                return;
            }
        }
        br.close();
    }
    // 모든 함수에서 곱셈이 발생할때 마다 MOD연산 수행
    private static long getMul(int s, int e) {
        long partMul = 1;
        while (s <= e) {
            if (s % 2 == 1) {
                partMul = partMul * tree[s] % MOD;
                s++;
            }
            if (e % 2 == 0) {
                partMul = partMul * tree[e] % MOD;
                e--;
            }
            s = s / 2;
            e = e / 2;
        }
        return partMul;
    }
    private static void changeVal(int index, long val) {
        tree[index] = val;
        while (index > 1) { //현재 노드의 양쪽 자식 노드를 찾아 곱해주는 로직
            index = index / 2;
            tree[index] = tree[index * 2] % MOD * tree[index * 2 + 1] % MOD;
        }
    }
    private static void setTree(int i) {
        while (i != 1) {
            tree[i / 2] = tree[i / 2] * tree[i] % MOD;
            i--;
        }}}

 

3. 메모

• 세그먼트 트리 사용
• https://rose-brown.tistory.com/159 와 매우 유사함