안녕하세요 이번 시간에는 세그먼트 트리에 대해 알아보는 시간을 갖도록 하겠습니다.
세그먼트 트리란 주어진 데이터들의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조입니다. 세그먼트 트리는 크게 3단계로 구현할 수 있습니다.
-
트리 크기 구하기 : 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 일차원 배열을 생성합니다.
--> 트리의 크기 = 2^(k+1) (k = 2^k >= N 을 만족하는 k의 최솟값) -
원본 데이터 채우기 : 시작 인덱스를 2^k로 설정한 후 순서대로 원본 데이터를 입력합니다.
--> 시작 인덱스 : 트리의 크기/2 -1 -
나머지 데이터 채우기 : 가장 뒤의 인덱스부터 시작하여 질의에 맞게 나머지 데이터를 로직대로 추가합니다.
--> 구간합을 구하는 경우 : tree[idx/2] = tree[idx/2] + tree[idx];
--> 최소 최대를 구하는 경우 : tree[idx/2] = Math.min(또는 max)(tree[idx/2], tree[idx]) -
인덱스 변환 : 현재 트리를 기준으로 입력받은 인덱스를 세그먼트 트리 인덱스로 변환합니다.
--> 세그먼트 트리 idx = 주어진 질의 idx + 시작 인덱스 (주어진 질의 idx + 2^k -1) -
두 노드의 값 스위칭 : 만약 문제에서 두 값의 순서를 서로 바꾸는 경우 시작 인덱스를 2씩 나누면서 조건에 맞게 트리에 데이터를 추가합니다.
-
질의값 구하기 : 구하고자 하는 질의값을 리턴합니다.
- 시작 인덱스%2 == 1 일 경우 해당 노드를 선택 후 시작 인덱스 --
- 종료 인덱스%2 == 0 일 경우 해당 노드를 선택 후 종료 인덱스 --
- 시작 인덱스 /= 2
- 종료 인덱스 /= 2
-
데이터 업데이트하기 : 구한 질의값을 출력합니다.
세그먼트 트리 문제는 집합 내의 원소들끼리 순서를 변경할 때의 질의값을 구하는 문제에서 주로 사용됩니다.
백준 2042(구간 합 구하기) 문제의 경우 중간의 수의 변경이 발생했을 때 시작에서 끝까지의 구간 합을 구하는 문제입니다. 중간의 수의 변경이 빈번하게 발생하기 때문에 데이터의 변경에도 시간이 비교적 적게 걸리는 세그먼트 트리를 이용합니다. 1차원 배열을 이용해 트리값을 초기화한 후 위의 단계대로 구간합을 구합니다. 이 때 두 노드를 바꿀 때 값과 시작 인덱스가 가리키는 값과의 차이를 시작 인덱스를 /= 2 한 트리에 지속적으로 더해줍니다. 즉 부모 노드에 두 값의 차이만큼 지속적으로 더해 구간합을 구해주며 질의값을 구할 때 선택된 노드의 값을 누적하여 더한 값을 출력합니다.
백준 10868(최솟값) 문제의 경우 정수 집합이 주어졌을 때 a번째 정수부터 b번째 정수 중 제일 작은 정수를 각각 구하는 문제입니다. 구간이 여러 개가 존재하기 때문에 세그먼트 트리를 이용합니다. 이 경우 두 노드를 바꾸는 경우는 없으며 부모 노드를 탐색하면서 최솟값을 구해 이를 리턴합니다.
백준 11505(구간 곱 구하기) 문제의 경우 N개의 수 중 중간의 수의 변경이 빈번하게 일어날 때 부분의 곱을 구하는 문제입니다. 구간 합 구하기와 마찬가지로 중간의 수의 변경이 빈번하게 발생하기 때문에 세그먼트 트리를 이용합니다. 여기서 주의할 점은 곱 연산이기 때문에 1차원 배열을 1로 초기화해주어야 하며 곱하기 연산을 *= 로 처리할 경우 % 연산이 먼저 처리되어 실질적으로 % 연산이 수행되지 않기 때문에 val = val * (수행 연산) % 나머지 이런 식으로 진행해야 합니다.
백준 11505 문제의 코드 예시를 통해 세그먼트 트리의 구현 코드를 보여드리겠습니다.
import java.util.*;
import java.io.*;
class Main{
static int N,M,K;
static int MOD = 1000000007;
static long[] tree;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 1. 트리의 크기 구하기
int h = 0;
int l = N;
while(l != 0){
l /= 2;
h++;
}
int size = (int) Math.pow(2,h+1);
// 2. 원본 데이터 채우기(시작 인덱스 구하기)
int start = size/2 -1;
tree = new long[size+1];
Arrays.fill(tree,1);
for(int i=1;i<=N;i++) tree[i+start] = Long.parseLong(br.readLine());
// 3. 나머지 데이터 채우기
int idx = size-1;
while(idx != 1){
tree[idx/2] = tree[idx/2] * tree[idx]%MOD;
idx--;
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<M+K;i++){
st = new StringTokenizer(br.readLine());
long a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
long c = Long.parseLong(st.nextToken());
// 4. 인덱스 변환 : start+b
// 5. 두 노드의 값 스위칭
if(a == 1) change(start+b, c);
// 6. 질의값 구하기
else if(a == 2){
b += start;
c += start;
// 7. 데이터 업데이트하기
sb.append(getVal(b,(int)c)).append("\n");
}
else return;
}
System.out.println(sb);
}
// 6. 질의값 구하기
static long getVal(int s, int e){
long val = 1;
while(s <= e){
if(s%2 == 1){
val = val * tree[s] % MOD;
s++;
}
if(e%2 == 0){
val = val * tree[e]%MOD;
e--;
}
s /= 2;
e /= 2;
}
return val;
}
// 5. 두 노드의 값 스위칭
static void change(int idx, long val){
tree[idx] = val;
while(idx > 1){
idx /= 2;
tree[idx] = tree[idx*2]%MOD * tree[idx*2+1]%MOD;
}
}
}