[알고리즘] 인덱스 트리란? (IndexedTree ) / 코딩테스트 인덱스 트리 /Java 구현/

⭐ 인덱스트리란? ⭐

리프 노드에 내가 쓸 값들을 저장해놓고, 부모들에는 해당 노드의 합들로 된 노드들을 만들어 구현해둔 트리입니다.

쉽게 말하자면 제일 밑 노드들은 값들, 그 위에 부모 노드들에는 값들의 정보(보통 노드의 부분합)를 모아둔 트리!

예시를 보시는게 좋을 것입니다.

 

---

언제 쓰이는가? 👀

인덱스 트리는 언제 쓰일까요?

 

1. 부분합을 계속해서 구해야할 때,

2. 특정 인덱스의 변경 또한 계속 일어날 수 있을 때 

 

이 두 조건이 만족할 때 주로 쓰입니다!

 

* left - right = N 이라 가정 

보통 구간 left ~ right 부분합을 구한다는 것은 left 부터 right 까지를 전부 더해야 하기에 O(N) 의 시간복잡도를 가집니다. 그래서 우리는 누적합 배열을 쓰죠! 누적합 배열에서 누적합을 구하는 것은 O(1) 상수시간 이니까요!

하지만 부분합 배열은 특정 인덱스를 변경하게되면, 어마어마한 배열 변경이 일어나게 되죠.. 그 변경시간 또한 O(N)입니다.

요약하자면, 

저 두 조건을 M번 실행하는 것은 일반적으로,

1. O(N)

2. O(1)

최종적으로 O(NM) 의 시간복잡도를 가집니다.

 

누적합 배열을 이용해도

1. O(1)

2. O(N)

이기에 O(NM) 의 시간복잡도를 가지죠.

 

하지만 인덱스 트리의 시간복잡도는 트리의 특성을 이용하기에

1. O(logN)

2. O(logN)

의 시간복잡도를 가집니다!!!!

최종적으로 O(MlogN) 의 시간복잡도를 가지죠!!

 

---

 

인덱스 트리 원리 🔢

인덱스 트리 원리는 그림으로 보면 간단합니다.

[8, 3, 26, 1, 7, 2, 4, 10] 이라는 숫자들의 부분합을 계속해서 구해야 하는 상황입니다.

트리의 인덱스 특성상 편리함을 위해 앞에 0 을 추가해줍니다! [0, 8, 3, 26, 1, 7, 2, 4, 10]

(트리 구성해보신분은 이 조그만한 작업 유무의 차이를 아실겁니다.. 😅)

우선 위의 그림처럼 이 배열을 이용해 인덱스 트리를 구성합니다.

리프노드에는 데이터들이 입력되어 있고, 리프노드가 N 개, 높이가 T라면 트리 총 노드의 개수는 2의 T승이 됩니다.

(원래 총 노드수는 2의 T승 이지만, 맨 앞 인덱스를 의미없는 데이터 0 으로 둬서 2의 T승개) 

인덱스 트리는 왠만하면 Full Binary Tree로 구성하는게 좋습니다! (방법은 밑에 코드로 설명하겠습니다)

 

트리가 구성이 된 상황이라면,

만약 제가 만약 3~5 인덱스의 합을 구하고 싶은 상황이라고 하죠.

 

보라색 그림과 같은 탐색이 이루어집니다.

3~5 는 (3-4) + 5 라고 할 수 있겠죠?

필요한 구간 노드까지만 탐색해서 최종합을 반환합니다.

 

---

인덱스 트리 구성 🌄  = > By JAVA

 

1. 트리 class 생성

트리를 생성해줍니다.

우선 트리를 만들 nums 배열의 길이를 이용해 Full Binary Tree의 height을 계산해주세요. 

개산한 Height 을 통해 쉽게 node 의 개수와 leaf노드의 개수도 구해줍니다! (⭐ 주석 참고 ⭐)

 

2. 트리화 해주기 

각 노드에 부분합을 넣어주는 과정입니다.

 

트리 루트에서 시작해서 왼쪽, 오른쪽  순으로 탐색하며, 자식 노드의 최종 합을 nodes[] 에 넣어줍니다.

@

node*2 = 왼쪽 자식

node*2+1 = 오른쪽 자식

@

3. 부분합 구해주는 getPartialSum 함수 구성 

nodes[] 를 이용하여 부분합을 구해주는 함수입니다. 

위에 보라색 선으로 표현했던 그림 있죠? 그걸 그대로 코드로 옮긴 것입니다!

재귀적으로 왼쪽, 오른쪽 순으로 들어가면서 만약 내가 구하고자 하는 구간에게 완전히 포함당하고 있는경우,  더해줍니다. 

 

4. 특정요소를 바꿔주는 update 함수 구성 ex) nums[3]=0

update도 마냥 쉽지는 않습니다!

한 곳만 바꾼다고 끝나지 않죠, 한 요소가 바뀌면 그 위에 있는 부모들의 부분합이 모두 바뀌는 것을 고려해주어야 합니다.

이것도 방식은 getPartialSum과 비슷한데, 만약 바꾸고자 하는 요소를 포함하고있는 노드라면, 바뀐만큼 을 더해줍니다.

재귀적으로 diff 를 내려주면서 해당구간을 포함한 노드라면 diff를 더해주는 방식입니다!

 

 

728x90

 

⭐ 코드 실행 및 최종 결과 ⭐

- Main 코드 -

Main 코드

- 출력값 -

 

 

- 인덱스트리 문제들 / 인덱스트리 예제 -

 

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

https://www.acmicpc.net/problem/2243

2243번: 사탕상자