PS/Algorithms
[Java] Segment Tree
CalicoCat22
2022. 3. 14. 13:36
https://www.acmicpc.net/blog/view/9
세그먼트 트리 (Segment Tree)
글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ..
www.acmicpc.net
https://steady-coding.tistory.com/126
[BOJ] 백준 2357번 : 최솟값과 최댓값 (JAVA)
문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M
steady-coding.tistory.com
tree.size = 4 * n
1번칸은 1~n 번 중 최소값
2번칸은 1~mid, 3번칸은 mid+1~n중 최소값
(mid = (lo + hi) / 2)
static int minUpdate(int lo, int hi, int node){
if (lo == hi){
return mintree[node] = pp[lo];
}
int mid = (lo + hi) / 2;
return mintree[node] = Math.min(minUpdate(lo, mid, node * 2), minUpdate(mid + 1, hi, node * 2 + 1));
}
static int maxUpdate(int lo, int hi, int node){
if (lo == hi){
return maxtree[node] = pp[lo];
}
int mid = (lo + hi) / 2;
return maxtree[node] = Math.max(maxUpdate(lo, mid, node * 2), maxUpdate(mid + 1, hi, node * 2 + 1));
}left, right 내부에 lo, hi가 있다면
그 범위 내의 최소값을 반환
static int minFind(int lo, int hi, int node, int left, int right){
if (right < lo || hi < left){
return Integer.MAX_VALUE;
}
if (left <= lo && hi <= right){
return mintree[node];
}
int mid = (lo + hi) / 2;
return Math.min(minFind(lo, mid, node * 2, left, right), minFind(mid + 1, hi, node * 2 + 1, left, right));
}
static int maxFind(int lo, int hi, int node, int left, int right){
if (right < lo || hi < left){
return -1;
}
if (left <= lo && hi <= right){
return maxtree[node];
}
int mid = (lo + hi) / 2;
return Math.max(maxFind(lo, mid, node * 2, left, right), maxFind(mid + 1, hi, node * 2 + 1, left, right));
}