세그먼트 트리 (Segment Tree)
·admin·조회수 8
#Algorithm
배열의 연속된 구간에 대한 질의(query)와 갱신(update)을 효율적으로 수행할 수 있도록 설계된 이진 트리 기반 자료구조
구간의 합, 구간의 최솟값, 구간의 최댓값 등을 빠르게 구할 때 사용할 수 있다.
구간의 합을 빠르게 구한다는 점에서 누적합과 비슷하지만, 배열의 값이 갱신 될 때 누적합의 갱신은 O(n)인 반면 세그먼트 트리의 갱신은 O(logN)이다.
구현
여기 그래프 이미지 넣어야함
java
static int arr[] = new int[N]; // 노드의 값을 저장하는 배열
static int tree[] = new int[N*4]; // 세그먼트 트리세그먼트 트리의 크기는 배열의 개수가 N일 때, N에 4를 곱한 크기만큼 할당하면 대충 맞다.
트리의 루트 노드는 계산의 편의성의 이유로 0번 인덱스가 아닌 1번 인덱스로 시작한다.
초기화 - Init
java
static void init(int start, int end, int index) {
// 리프 노드에 도달 시 값을 트리에 삽입
if(start == end) {
return tree[index] = arr[start];
}
int mid = (start + end) / 2;
// 비트마스킹을 활용하면 더 빠르게 트리를 순회할 수 있다.
int left = init(start, mid, index << 1); // index << 1 == index * 2
int right = init(mid+1, end, (index << 1) | 1); // (index << 1) | 1 == index * 2 + 1
return tree[index] = left + right;
}질의 - Query
java
static int query(int start, int end, int index, int left, int right) {
// 유효하지 않은 범위
if(left > end || right < start) return 0;
// 범위 내에 있을 경우
if(left <= start && end <= right) return tree[index]
int mid = (start + end) / 2;
// 범위가 맞지 않을 경우
return query(start, mid, index<<1, left, right) + query(mid+1, end, (index<<1)|1, left, right);
}갱신 - Update
java
static void update(int start, int end, int index, int target, int delta) {
// 유효하지 않은 범위
if(target < start || end < target) return;
// 범위 안에 있으면 노드 갱신
tree[index] += value;
// 리프 노드면 개신 종료
if(start == end) return;
// 현재 노드가 리프 노드가 아니면 좌/우 자식 노드 갱신
int mid = (start + end) / 2;
update(start, mid, index<<1, target, delta);
update(mid+1, end, (index<<1)|1, target, delta);
}