Segment Tree
NOTE
•
어떤 데이터가 존재할 떄, 특정 구간의 결과값을 구하는데 사용하는 자료구조
◦
아래와 같이 주어진 배열이 존재할 때, 3~5번째 구간의 합을 구하시오
◦
하지만 배열의 크기가 커지면 어떻게 해야하는가?
⇒ 구간별 합을 저장해두면 빠르게 찾을 수 있다!
•
하지만 미리 합을 저장해두어도 값이 수정되거나 하면 나머지가 모두 수정되어야함
•
그렇기에 Segment Tree는 이진트리 구조를 가진다
segment의 개수는 2의 제곱수여야 한다
public SegmentTree(int[] inputList, String calculationMethod) {
this.calculationMethod = calculationMethod;
this.inputListLength = inputList.length;
this.inputEndIndex = this.inputListLength - 1;
this.inputList = new int[this.inputListLength];
for(int i = 0; i < this.inputListLength; i++) {
this.inputList[i] = inputList[i];
}
this.level = (int) Math.ceil(Math.log(this.inputListLength) / Math.log(2)) + 1;
this.length = (int) Math.pow(2, this.level); // 완전이진트리가 아니라 1줄더 생길 수 있으니 넉넉하게 잡음
this.resultList = new int[this.length];
this.make(0, this.inputListLength-1, 1);
}
Java
복사
segment tree 초기화
public int make(int inputStartIndex, int inputEndIndex, int treeIndex) {
// 1. 리프노드라면 현재값을 채우고 값을 가지고 올라온다
if (inputStartIndex == inputEndIndex) {
this.resultList[treeIndex] = this.inputList[inputStartIndex];
return this.resultList[treeIndex];
}
// 2. 왼/오를 구분하기 위해 중간값을 가진다
int inputMidIndex = (inputStartIndex + inputEndIndex) / 2;
// 3. 왼쪽과 오른쪽 값을 가져온다
int left_result = this.make(inputStartIndex, inputMidIndex, treeIndex * 2);
int right_result = this.make(inputMidIndex + 1, inputEndIndex, treeIndex * 2 + 1);
// 4. 두 값의 연산결과를 현위치에 저장하고 해당 값을 리턴
this.resultList[treeIndex] = this.method(left_result, right_result);
// 5.
return this.resultList[treeIndex];
}
Java
복사
segment tree 생성
public int getRangeProcess(int inputStartIndex, int inputEndIndex, int treeIndex, int rangeStartIndex, int rangeEndIndex) {
// 완전하게 벗어난 범위는 무효화한다
if ((inputEndIndex < rangeStartIndex) || (inputStartIndex > rangeEndIndex)) {
return 0;
}
// 구간에 완전히 들어간다 (리프 일수도 아닐수도 있다)
// 그대로 값 들고옴 (그냥 밑으로 가라)
if ((inputStartIndex >= rangeStartIndex) && (inputEndIndex <= rangeEndIndex)) {
return this.resultList[treeIndex];
}
// 좌우값 위치 구하기
int inputMidIndex = (inputStartIndex + inputEndIndex) / 2;
int leftResult = this.getRangeProcess(inputStartIndex, inputMidIndex, treeIndex * 2, rangeStartIndex, rangeEndIndex);
int rightResult = this.getRangeProcess(inputMidIndex + 1, inputEndIndex, treeIndex * 2 + 1, rangeStartIndex, rangeEndIndex);
return this.method(leftResult, rightResult);
}
public int getRange(int rangeStartIndex, int rangeEndIndex) {
return this.getRangeProcess(this.inputStartIndex, this.inputEndIndex, this.treeIndex, rangeStartIndex, rangeEndIndex);
}
// 합, 최대값, 최대공약수 구하는 식
public int method(int leftResult, int rightResult) {
switch (this.calculationMethod) {
case "sum":
return leftResult + rightResult;
case "max":
return Math.max(leftResult, rightResult);
case "gcd":
return this.gcd(leftResult, rightResult);
}
return leftResult + rightResult;
}
Java
복사
내가 구하고자 하는 구간
세그먼트 트리 - 데이터 변경
NOTE
•
특정 노드의 값을 2더한다
•
합의 경우는 그냥 다 더해주면 되지만 다른경우는 좀 까다로워진다
1.
리프노드는 그대로 갱신
2.
부모노드는 왼/오 를 계산해야한다
3.
상관없는 노드는 그대로 리턴한다
public int updateProcess(int inputStartIndex, int inputEndIndex, int treeIndex, int updateIndex, int updateValue) {
// 구간에 영향을 미치지 않는다 (그대로 리턴)
if ((updateIndex < inputStartIndex) || (updateIndex > inputEndIndex)) {
return this.resultList[treeIndex];
}
// 업데이트하고자 하는 리프위치에 도달 (그냥 바꿔라)
if (inputStartIndex == inputEndIndex) {
this.resultList[treeIndex] = updateValue;
return this.resultList[treeIndex];
}
// 이후 계산해주기
int inputMidIndex = (inputStartIndex + inputEndIndex) / 2;
int leftResult = this.updateProcess(inputStartIndex, inputMidIndex, treeIndex * 2, updateIndex, updateValue);
int rightResult = this.updateProcess(inputMidIndex + 1, inputEndIndex, treeIndex * 2 + 1, updateIndex, updateValue);
this.resultList[treeIndex] = this.method(leftResult, rightResult);
return this.resultList[treeIndex];
}
Java
복사
