문제
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 2 * 6 * 4 * 5 = 240을 출력하면 되는 문제이다. 단, 모든 결과값은 1,000,000,007로 나눈 나머지를 출력한다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그 다음 M+K개의 줄에는 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째부터 c번째까지의 곱을 출력한다.
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.
예제
입력:
5 2 2
1 2 3 4 5
1 3 6
2 2 5
1 5 2
2 3 5출력:
240
36풀이
핵심 아이디어: 세그먼트 트리의 각 노드에 구간 곱을 저장한다. 구간 외 쿼리의 기본값을 1(곱셈의 항등원)로 설정하고, 모든 연산에서 1,000,000,007로 나머지를 취한다.
- 트리 구성: 리프 노드에 원소 값을 저장하고, 내부 노드에 두 자식의 곱(mod)을 저장하며
buildTree로 초기화한다. - 업데이트: 특정 인덱스의 값을 변경하면, 루트부터 해당 리프까지의 경로상 모든 노드 값을 갱신한다.
update함수는 범위 밖이면 현재 값을 그대로, 리프이면 새 값을, 내부 노드이면 두 자식 값의 곱을 저장한다. - 쿼리: 쿼리 범위
[left, right]와 현재 노드 범위[nodeLeft, nodeRight]가 완전히 겹치면 노드 값을 반환하고, 겹치지 않으면 1을 반환한다(곱셈 단위원). 부분적으로 겹치면 두 자식을 재귀 호출하여 곱한다. - 모듈러 처리:
int타입으로 나머지를 저장하되, 중간 곱셈 과정은 오버플로 방지를 위해long으로 계산 후 mod 처리한다.
코드
package ASP_study.day299;
public class Day291BOJ11505구간곱Seg {
static StringBuilder sb = new StringBuilder();
static Reader in = new Reader();
static int N, M, K;
static final int mod = 1000000007;
static int[] tree, arr;
public static void main(String[] args) throws Exception {
N = in.nextInt();
M = in.nextInt();
K = in.nextInt();
tree = new int[4 * N];
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
buildTree(1, 0, N - 1);
for (int i = 0; i < M + K; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
if (a == 1) {
update(b - 1, c, 1, 0, N - 1);
} else {
sb.append(query(b - 1, c - 1, 1, 0, N - 1)).append("\n");
}
}
System.out.println(sb);
}
static long buildTree(int node, int nodeLeft, int nodeRight) throws Exception {
if (nodeLeft == nodeRight) {
return tree[node] = arr[nodeLeft];
}
int mid = nodeLeft + (nodeRight - nodeLeft) / 2;
long leftValue = buildTree(node * 2, nodeLeft, mid);
long rightValue = buildTree(node * 2 + 1, mid + 1, nodeRight);
return tree[node] = (int) (((leftValue % mod) * (rightValue % mod)) % mod);
}
static long query(int left, int right, int node, int nodeLeft, int nodeRight) {
if (nodeRight < left || right < nodeLeft) {
return 1;
}
if (left <= nodeLeft && nodeRight <= right) {
return tree[node];
}
int mid = nodeLeft + (nodeRight - nodeLeft) / 2;
return ((query(left, right, node * 2, nodeLeft, mid) % mod)
* (query(left, right, node * 2 + 1, mid + 1, nodeRight) % mod)) % mod;
}
static long update(int idx, int newValue, int node, int nodeLeft, int nodeRight) {
if (nodeRight < idx || idx < nodeLeft) {
return tree[node];
}
if (nodeLeft == nodeRight) {
return tree[node] = newValue;
}
int mid = nodeLeft + (nodeRight - nodeLeft) / 2;
long leftValue = update(idx, newValue, node * 2, nodeLeft, mid);
long rightValue = update(idx, newValue, node * 2 + 1, mid + 1, nodeRight);
return tree[node] = (int) (((leftValue % mod) * (rightValue % mod)) % mod);
}
}
class Reader {
final int SIZE = 1 << 13;
byte[] buffer = new byte[SIZE];
int index, size;
int nextInt() throws Exception {
int n = 0;
byte c;
while ((c = read()) <= 32)
;
do
n = (n << 3) + (n << 1) + (c & 15);
while (isNumber(c = read()));
return n;
}
boolean isNumber(byte c) {
return 47 < c && c < 58;
}
byte read() throws Exception {
if (index == size) {
size = System.in.read(buffer, index = 0, SIZE);
if (size < 0)
buffer[0] = -1;
}
return buffer[index++];
}
}복잡도
- 시간: O((N + M + K) log N) — 트리 구성 O(N), 업데이트/쿼리 각 O(log N)
- 공간: O(N) — 세그먼트 트리 크기 4N