세그먼트 트리 (Segment Tree)
특징
구간 합, 최소값/최대값 등을 빠르게 구할 수 있는 자료구조
주로 배열 형태의 데이터를 다룰 때 사용
세그먼트 트리는 이진 트리의 일종으로, 노드의 값은 해당 구간의 값을 나타냄
- 구간 합 문제의 경우
- 리프노드(leaf node) : 해당하는 위치의 배열의 수
- 그 외 노드 : 왼쪽 자식과 오른쪽 자식의 합
구조
기본적으로 이진 트리 구조를 가짐 -> 리프 노드가 아닌 모든 노드는 1개 이상, 2개 이하의 자식 노드를 보유함
- 기존 이진 트리 : 모든 노드가 고유의 값을 가짐
- 세그먼트 트리 : 부모 노드가 자식 노드들의 합을 가짐
루트 노드의 번호가 1번으로 시작하고, 현재 노드의 번호가 X 일때, 자식들의 노드 번호
- 왼쪽 자식 :
2 * X - 오른쪽 자식 :
2 * X + 1
전체 구간의 크기는 리프 노드의 개수와 같음
전체 필요 노드의 수 : 2의 제곱꼴인 경우, 2 * n-1 개
트리의 높이 : 2가지 경우로 나뉨
n이 2의 제곱꼴인 경우- 아닌 경우
세그먼트 트리의 연산
주로 아래와 같은 연산을 수행
- 구간 합 구하기
- 최소값/최대값 구하기
- 구간 갱신
구현
세그먼트 트리는 보통 배열로 구현함
생성 및 구성(생성자, init 메소드)
세그먼트 트리의 리프 노드에 배열로 전달된 값들을 넣고, 그 부모 노드들에 각각의 구간 합을 삽입하는 방식으로 진행
재귀 방식으로 구현이 가능함
class SegmentTree{
long tree[]; //각 원소가 담길 트리
int treeSize; // 트리의 크기
public SegmentTree(int arrSize){
// 트리 높이 구하기
int h = (int) Math.ceil(Math.log(arrSize)/ Math.log(2));
// 높이를 이용한 배열 사이즈 구하기
this.treeSize = (int) Math.pow(2,h+1);
// 배열 생성
tree = new long[treeSize];
}
// arr: 원소배열, node: 현재노드, start: 현재구간 배열 시작, end: 현재구간 배열 끝
public long init(long[] arr, int node, int start,int end){
// 배열의 시작과 끝이 같다면 leaf 노드이므로
// 원소 배열 값 그대로 담기
if(start == end){
return tree[node] = arr[start];
}
// leaf 노드가 아니면, 자식노드 합 담기(재귀 수행)
// node*2: 왼쪽 자식, node*2 + 1 오른쪽 자식
return tree[node] = init(arr,node*2,start,(start+ end)/2
+ init(arr,node*2+1,(start+end)/2+1,end);
}
}- 세그먼트 트리의 높이 및 배열 사이즈
- Math.log 는 자연 로그이므로, log2 로 한번 더 나눠줘야함
- Math.ceil : 원소 배열의 길이가 2의 제곱꼴이 아닐 때 +1 을 해주기 위한 올림처리
데이터 변경(update 메소드)
중간에 값이 변경되었을 경우, 재귀적으로 기존의 값과 현재 값의 차이만큼 영향 받는 모든 노드에 연산을 수행하여 변경해주는 방식
원본 배열의 값도 변경해주어야함
// node: 현재노드 idx, start: 배열의 시작, end:배열의 끝
// idx: 변경된 데이터의 idx, diff: 원래 데이터 값과 변경 데이터값의 차이
public void update(int node, int start, int end, int idx, long diff){
// 만약 변경할 index 값이 범위 바깥이면 확인 불필요
if(idx < start || end < idx) return;
// 차를 저장
tree[node] += diff;
// 리프노드가 아니면 아래 자식들도 확인
if(start != end){
update(node*2, start, (start+end)/2, idx, diff);
update(node*2+1, (start+end)/2+1, end, idx, diff);
}
}- 변경된 idx 와 관련된 노드들이 다 변경되어야함
- 루트노드에서부터 재귀수행
- 놓치지 말아야할점으로 원본 배열의 값이 변경되어 세그먼트 트리의 값이 변경되므로 원본 배열의 값도 변경을 해야함
구간 합 구하기(sum 메소드)
// node: 현재 노드, start : 배열의 시작, end : 배열의 끝
// left: 원하는 누적합의 시작, right: 원하는 누적합의 끝
public long sum(int node, int start, int end, int left, int right){
// 범위를 벗어나게 되는 경우 더할 필요 없음
if(left > end || right < start){
return 0;
}
// 범위 내 완전히 포함 시에는 더 내려가지 않고 바로 리턴
if(left <= start && end <= right){
return tree[node];
}
// 그 외의 경우 좌 / 우측으로 지속 탐색 수행
return sum(node*2, start, (start+end)/2, left, right)+
sum(node*2+1, (start+end)/2+1, end, left, right);
}- 구간의 합을 구하는 경우는 4가지가 있을 수 있음
- [left, right] 와 [start, end] 가 겹치지 않는 경우 → 겹치지 않으면 불필요한 구간
- [left, right] 와 [start, end] 가 완전히 일치하는 경우 → 현재 그 구간합을 보유한 노드가 정답
- [start, end] 가 [left, right] 를 완전히 포함하거나 한쪽만 겹치는 경우 → left/right 의 정확한 구간보다 더 넓은 범위 ⇒ 더 아래로 내려가서 찾아야함
- 예시
# 3 ~ 5 까지의 구간합 구하기 1번 루트 노드(1~7) 이므로 자식 확인 (return 자식2 + 자식3) 자식 2(1~4) 안에는 3 ~ 4 가 해당 => 자식 확인 (return 자식4 + 자식 5) 자식 4(1~2) 안에는 구하고자 하는 3 ~ 5에서 벗어남 -> 0 반환 **자식 5(3~4) 는 구하고자 하는 3 ~ 5 에 완전히 포함 -> 값 반환** 자식 3(5~7) 안에 5 해당 (return 자식6 + 자식7) 자식 6(5~6) 안에 5 해당 (return 자식12 + 자식13) **자식 12(5) 구하고자 하는 3 ~ 5 에 완전 포함 -> 값 반환** 기타 나머지 자식들은 다 포함하지 않음 -> 0반환 최종 자식 5번 노드 + 자식 12번 노드 = 3 ~ 5 까지의 합이 반환
구현 코드
static class SegmentTree {
long[] tree;
int treeSize;
public SegmentTree(int size) {
int h = (int) Math.ceil(Math.log(size) / Math.log(2));
this.treeSize = (int) Math.pow(2, h + 1);
tree = new long[treeSize];
}
public long init(long[] arr, int node, int start, int end) {
// leaf 노드 -> 원소 배열의 값을 그대로 담음
if (start == end) return tree[node] = arr[start];
// leaf 노드가 아닌 경우 자식 노드의 합을 담음
return tree[node] = init(arr, node * 2, start, (start + end) / 2)
+ init(arr, node * 2 + 1, (start + end) / 2 + 1, end);
}
public void update(int node, int start, int end, int idx, long diff) {
// 변경할 index 값이 범위를 벗어나면 확인할 필요가 없음
if (idx < start || idx > end) return;
// 원래 데이터 값과 변경 데이터의 차이저장
tree[node] += diff;
// 리프노드가 아니면 자식노드들에 대해서도 수행
int mid = (start + end) / 2; // 중간 인덱스
if (start != end) {
update(node * 2, start, mid, idx, diff);
update(node * 2 + 1, mid + 1, end, idx, diff);
}
}
public long sum(int node, int start, int end, int left, int right) {
// 범위를 벗어나는 경우
if (left > end || right < start) return 0;
// 범위 내 완전 포함 시 바로 반환
if (left <= start && end <= right) return tree[node];
// 좌 / 우측 자식 확인
int mid = (start + end) / 2;
return sum(node * 2, start, mid, left, right)
+ sum(node * 2 + 1, mid + 1, end, left, right);
}
}세그먼트 트리 - 느린 전파
구간에 있는 모든 값을 변경해야하는 경우
이전 방식을 그대로 활용할 경우, update 메소드를 구간 내의 원소 개수만큼 반복 호출해야함
⇒ 시간복잡도는 최악의 경우 (전체 구간을 업데이트 하는 경우) 이 되며,
위 작업을 M 회 수행할 경우 시간 복잡도는 이 됨
너무 긴 시간을 소요하게되며, 이를 더 빠르게 수행할 수 있게 하는 것
⇒ 느린 전파(Lazy Propagation) 기법
느린 전파(Lazy Propagation)
말 그대로, 게으르게 전파 하는 방식
구간 내의 모든 값을 갱신할 때, 해당 구간을 대표하는 대표 노드에 변경되는만큼의 정보를 저장해두고, 당장 전파하지 않고 추후에 전파하는 방식
이 방식으로 앞서 이 소요되었던 작업이 만에 완료될 수 있음
예시 (일반 세그먼트 트리)
arr[1] ~ arr[6] 의 구간 내 데이터를 모두 5씩 더해주는 경우
대표 노드에 변경되는 정보를 저장해야함 → lazy 라는 이름의 배열에 저장
변경 구간의 대표노드 : 빨간색 / 대표노드의 lazy : 파란색
2번 노드: arr[1] ~ arr[4] 대표
6번 노드 : arr[5] ~ arr[6] 대표
업데이트 수행 후 arr[2] ~ arr[5] 까지의 합의 정보를 구하는 경우
세그먼트 트리의 합을 구하는 로직에 따라, 9번, 5번, 12번 노드를 방문하여 그 값을 반환하고 전부 더하려고함
그러나 이때 lazy 의 정보는 2번 과 6번 노드에만 저장이 되어 있어, 전파가 완료되지 않았음 ⇒ 답은 틀린 답이 얻어질 것
세그먼트 트리에서 느린 전파를 하는 방법
자식 노드에 도달하기 위해서는 반드시 부모 노드를 거처야하는 구조를 활용
→ 부모 노드에 lazy 정보가 있다면? ⇒ 자식 노드에게 전파시킴
예시와 함께 확인해보자
1. arr[1] ~ arr[6] 의 모든 구간에 +5
루트에서부터 탐색 시작
구간의 대표를 찾아 lazy 업데이트 수행
최상단 노드(루트 노드)에서 시작하여, 업데이트 구간의 대표 노드를 찾으면 해당 노드에 lazy 를 저장하고 바로 적용 시킨 뒤, 자신의 자식 노드들에 전파시킴
앞서 봤던 그림에서는 대표 노드에만 lazy 를 저장하나, 실제 코드에서는 위 그림과 같이 동작함
- 어떻게 값을 바로 반영하는가? 자신이 대표노드이므로, 그 구간의 변화하는 노드의 수 또한 정보를 알 수 있음 ⇒ 구간 길이만큼 변경되는 값에 곱해서 더해주면됨
2. arr[3] ~ arr[4] 의 모든 구간에 +3
5번 노드에 기존 lazy 값이 있었으므로, 그에 대한 반영이 필요한 경우.
3을 더해서 업데이트해야하므로, 8만큼을 업데이트 한 뒤에 자식 노드에 lazy 를 전파시키는 방식으로 진행됨
(실제 코드는 업데이트를 먼저하고, lazy 를 또 다시 반영하는 방식으로 수행됨)
3. arr[1] ~ arr[7] 까지 모든 구간의 합 구하기
위에서 lazy 를 아래쪽으로 전파시켰는데, 전파되는 대표노드의 부모 노드들에는 반영이 안되고 있음
→ 세그먼트 트리의 재귀적인 성격을 활용하면 해결할 수 있음
업데이트 시, lazy 를 반영한 뒤, 재귀로 빠져나오기 전에 부모 노드에 자식 노드들의 합을 다시 입력해줌으로써 간단히 해결이 가능함
구현 코드
public class SegmentTree{
int size;
long[] tree;
long[] lazy;
public SegmentTree(int n){
int h = (int) Math.ceil(Math.log(n) / Math.log(2));
this.size = (int)Math.pow(2, h+1);
this.tree = new long[size];
this.lazy = new long[size];
}
// 전체 Segment Tree를 만드는 메소드. 느린 전파 이전과 동일!
public long init(long[] nums, int node_idx, int start, int end){
if(start == end){
return tree[node_idx] = nums[start];
}
int mid = (start+end)/2;
return tree[node_idx] = init(nums, node_idx*2, start, mid) +
init(nums, node_idx*2+1, mid+1, end);
}
// 느린 전파를 실제로 수행하는 메소드!
private void lazy_update(int node_idx, int start, int end){
// 만약 현재 노드에 lazy 정보가 없다면! 반환
if(lazy[node_idx] == 0){
return;
}
// 있으면 구간의 길이 * lazy 값 반영!
tree[node_idx] += ((end - start +1) * lazy[node_idx]);
if(end != start){
lazy[node_idx * 2] += lazy[node_idx];
lazy[node_idx * 2 + 1] += lazy[node_idx];
}
// 반영 후 0으로 다시 초기화
lazy[node_idx] = 0;
}
public void update(int node_idx, int start, int end, int left, int right, long diff){
// 각 대표 노드에 갈 때마다 lazy가 있는지 확인하여 업데이트
lazy_update(node_idx, start, end);
if(right < start || left > end){
return;
}
// diff값이 lazy 이므로 현재 노드에 전달
if(left <= start && end <= right){
lazy[node_idx] += diff;
lazy_update(node_idx, start, end);
return;
}
update(node_idx * 2, start, (start+end)/2, left, right, diff);
update(node_idx*2+1, (start+end)/2+1, end, left, right, diff);
// 이것이 바로 위로 다시 전파하는 코드. 부모 노드에도 update가 전달됨
tree[node_idx] = tree[node_idx * 2] + tree[node_idx*2+1];
}
public long sum(int node_idx, int start, int end, int left, int right){
// 업데이트 후, sum을 하기 전에 lazy가 있다면 또 업데이트를 해야함!
lazy_update(node_idx, start, end);
if(left > end || right < start){
return 0;
}
if(left <= start && end <= right){
return tree[node_idx];
}
return sum(node_idx*2, start, (start+end)/2, left, right) +
sum(node_idx*2+1, (start+end)/2+1, end, left, right);
}
}