✔ 구간 곱 구하기
문제 분석하기
기본 틀인 세그먼트 트리에다가 조건에 따라 자유자재로 기존의 알고리즘 코드를 수정할 수 있도록 함
손으로 풀어보기
- 1차원 배열을 이용해 트리의 값을 초기화
- 트리 배열의 크기가 N = 5이므로 2^k >= N을 만족하는 k의 값은 3
- 배열의 크기는 2³ * 2 = 16
- 시작 인덱스는 2³ = 8
- 곱셈이기 때문에 초깃값을 1로 저장해주고, 부모 노드를 양쪽 자식 노드의 곱으로 표현
- 이때 지속적으로 MOD 연산을 수행해 값의 범위가 1000000007이 넘지 않도록 구현
- 질의값 연산 함수와 데이터 업데이트 함수를 수행하고, 질의와 관련된 결괏값을 출력
- 값을 업데이트하거나 구간 곱을 구하는 각 곱셈마다 모두 MOD 연산을 수행
슈도코드 작성하기
tree(세그먼트 트리 배열)
N(수의 개수) M(변경이 일어나는 개수) K(구간 곱을 구하는 개수)
MOD(1000000007)
treeSize 구하기 (Math.pow(2, 트리의 높이 + 1))
leftNodeStartIndex 구하기 (treeSize / 2 - 1)
tree 초기화하기(모든 값을 1로 초기화)
tree 배열의 리프 노드 영역에 데이터 입력받기
setTree(트리의 크기)
for(M + K만큼 반복하기) {
a(질의 유형) b(시작 인덱스) c(변경값 또는 종료 인덱스)
a가 1일 때 -> changeVal(tree에서 시작 인덱스, c(변경값))
a가 2일 때 -> getMul(tree에서 시작 인덱스, tree에서 종료 인덱스)
}
setTree(트리의 마지막 인덱스) {
while(인덱스가 루트가 아닐 때까지 반복하기) {
트리의 인덱스 / 2 부분(부모 노드)에 현재 index의 트리 값 곱하기 % MOD
index 1개 감소
}
}
changeVal(시작 인덱스, 변경값) {
현재 index에 변경값 저장하기
while(시작 인덱스가 1보다 크다) {
시작 인덱스 = 시작 인덱스 / 2
시작 인덱스의 트리 값 = 시작 인덱스 * 2의 트리 값 % MOD * 시작 인덱스 * 2 + 1의 트리 값 % MOD
}
}
getMul(시작 인덱스, 종료 인덱스) {
while(시작 인덱스와 종료 인덱스가 교차될 때까지) {
if(시작 인덱스 % 2 == 1) 해당 노드의 값을 구간 곱에 곱하기 % MOD
if(종료 인덱스 % 2 == 0) 해당 노드의 값을 구간 곱에 곱하기 % MOD
시작 인덱스 = 시작 인덱스 / 2
종료 인덱스 = 종료 인덱스 / 2
}
구간 곱 결과 리턴하기
}
코드 구현하기
/**
* 11505) 구간_곱_구하기
*/
public class D073_11505 {
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());
// N(수의 개수)
int N = Integer.parseInt(st.nextToken());
// M(변경이 일어나는 개수)
int M = Integer.parseInt(st.nextToken());
// K(구간 곱을 구하는 개수)
int K = Integer.parseInt(st.nextToken());
// treeHeight(트리의 높이) 구하기
int treeHeight = 0;
int length = N;
while (length != 0) {
length /= 2;
treeHeight++;
}
// treeSize(트리 배열의 크기) 구하기
int treeSize = (int) Math.pow(2, treeHeight + 1);
// leftNodeStartIndex(리프 노드 시작 인덱스) 구하기
int leftNodeStartIndex = treeSize / 2 - 1;
// MOD(1000000007)
MOD = 1000000007;
// tree(세그먼트 트리 배열)
tree = new long[treeSize + 1];
// 트리 초기화하기(모든 값을 1로 초기화)
for (int i = 0; i < tree.length; i++) {
tree[i] = 1;
}
// tree 배열의 리프 노드 영역에 데이터 입력받기
for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
tree[i] = Long.parseLong(br.readLine());
}
// setTree(트리의 크기)
setTree(treeSize - 1);
for (int i = 0; i < M + K; i++) {
st = new StringTokenizer(br.readLine());
// a(질의 유형)
int a = Integer.parseInt(st.nextToken());
// b(시작 인덱스)
int b = Integer.parseInt(st.nextToken());
// c(변경값 또는 종료 인덱스)
long c = Long.parseLong(st.nextToken());
// a가 1일 때
if (a == 1) {
// changeVal(tree에서 시작 인덱스, c(변경값))
changeVal(leftNodeStartIndex + b, c);
}
// a가 2일 때
else if (a == 2) {
// getMul(tree에서 시작 인덱스, tree에서 종료 인덱스)
b = b + leftNodeStartIndex;
c = c + leftNodeStartIndex;
System.out.println(getMul(b, (int) c));
} else {
return;
}
}
br.close();
}
// 초기 트리를 구성하는 함수
public static void setTree(int i) {
// 인덱스가 루트가 아닐 때까지 반복하기
while (i != 1) {
// 트리의 인덱스 / 2 부분(부모 노드)에 현재 index의 트리 값 곱하기 % MOD
tree[i / 2] = tree[i / 2] * tree[i] % MOD;
// index 1개 감소
i--;
}
}
// 값을 변경하는 함수
public static void changeVal(int index, long val) {
// 현재 index에 변경값 저장하기
tree[index] = val;
while (index > 1) {
// 시작 인덱스 = 시작 인덱스 / 2
index = index / 2;
// 시작 인덱스의 트리 값 = 시작 인덱스 * 2의 트리 값 % MOD * 시작 인덱스 * 2 + 1의 트리 값 % MOD
tree[index] = tree[index * 2] % MOD * tree[index * 2 + 1] % MOD;
}
}
// 구간 곱을 구하는 함수
public static long getMul(int s, int e) {
long partMul = 1;
// 시작 인덱스와 종료 인덱스가 교차될 때까지
while (s <= e) {
if (s % 2 == 1) {
// 해당 노드의 값을 구간 곱에 곱하기 % MOD 하거나 시작 인덱스 증가
partMul = partMul * tree[s] % MOD;
s++;
}
if (e % 2 == 0) {
// 해당 노드의 값을 구간 곱에 곱하기 % MOD 하거나 종료 인덱스 감소
partMul = partMul * tree[e] % MOD;
e--;
}
// 시작 인덱스 = 시작 인덱스 / 2
s = s / 2;
// 종료 인덱스 = 종료 인덱스 / 2
e = e / 2;
}
// 구간 곱 결과 리턴하기
return partMul;
}
}
'Coding Test > 알고리즘 실전' 카테고리의 다른 글
[11438] LCA 2 (0) | 2023.10.04 |
---|---|
[11437] LCA (0) | 2023.10.04 |
[10868] 최솟값 (0) | 2023.10.03 |
[2042] 구간 합 구하기 (0) | 2023.10.03 |
[1991] 트리 순회 (0) | 2023.10.02 |