문제 풀이

세그먼트 트리를 이용해서 푸는 문제.
세그먼트트리에는 구간의 곱을 저장해준다. % 1000000007는 잊지않고 꼭 해준다.

find 함수에서는 구간의 곱을 찾는데 이전에 풀었던 구간 합 구하는 문제에서는 범위를 벗어나는 경우에 0을 반환했지만 이번에는 '곱'을 하는 것이기때문에 범위를 벗어나는 경우 1을 반환해 결과값에 영향을 주지 않도록 한다.

입력 a, b, c에서 a가 1일 경우 특정 원소의 값을 바꿔야되는데 그렇게 되면 세그먼트 트리를 업데이트를 해야한다.

범위를 벗어나는 경우에는 현재 세그먼트 트리의 노드값을 그대로 반환해 유지해준다.
start == end로 바꿔야하는 인덱스에 도달했을 경우 그 값을 바꿔야하는 값으로 바꿔준다.
그리고 나서 부모 노드로 차근 차근 다시 위로 올라가면서 바꾼 값을 토대로 업데이트해준다.

기존의 구간 합 문제에서는 update를 기존 값과 바꿔야하는 값의 차이로 부모 노드부터 바꿔주었지만
구간 곱 문제에서는 0으로 바뀌거나 0에서 또 다른 값으로 바뀔 때 부모 노드부터 바꿀 수 있는 방법이 없기 때문에 하위에서부터 상위로 값을 바꾸도록 한다.

문제 링크

boj/11505

소스코드

PS/11505.java

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;


public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static int []arr;
  static long []segTree;

  static double baseLog(double x, double base) {
      return Math.log(x) / Math.log(base);
  }

  static long make_seg(int node , int start, int end)
  {
      if(start == end)
          return segTree[node] = arr[start];
      segTree[node] =(make_seg(node * 2, start , (start + end) / 2) *
      make_seg(node * 2 + 1, (start+end)/2 + 1 , end) ) % 1000000007;
      return segTree[node];
  }

  static long find(int node, int start , int end , int left, int right)
  {
      if(end < left || right < start)
          return 1;
      if(left<= start && end <= right)
          return segTree[node];
      long ret = (find(node * 2, start, (start + end) / 2, left, right) * find(node * 2 + 1, (start + end) / 2 + 1, end, left, right)) % 1000000007;
      return ret;
  }

  static long update_seg(int node, int start, int end, int idx,int to)
  {
      if(idx < start || idx > end) {
          return segTree[node];
      }
      if(start == end) {
          return segTree[node] = to;

      }
      segTree[node] = (update_seg(node * 2 ,start, (start+end) / 2 , idx, to)*
      update_seg(node * 2 + 1, (start+end) / 2 + 1, end , idx,to))% 1000000007;
      return segTree[node];
  }
  public static void main(String[] args) throws IOException {

      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 = (int) Math.ceil(baseLog(n,2));
      int treeSize = (int) Math.pow(2,treeHeight+1);
      arr = new int[n+2];
      for(int i=0;i<n;i++)
      {
          arr[i] = Integer.parseInt(br.readLine());
      }

      segTree = new long[treeSize+2];
      make_seg(1,0,n-1);

      for(int i=0;i<m+k;i++)
      {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          int c = Integer.parseInt(st.nextToken());
          if(a == 1)
          {
              update_seg(1,0,n-1, b-1,c);
          }
          else {
          bw.write(find(1,0,n-1,b-1,c-1) %1000000007 +"\n");
              bw.flush();
          }

      }


  }

}