인덱스트리1
[알고리즘] 인덱스 트리란? (IndexedTree ) / 코딩테스트 인덱스 트리 /Java 구현/
⭐ 인덱스트리란? ⭐ 리프 노드에 내가 쓸 값들을 저장해놓고, 부모들에는 해당 노드의 합들로 된 노드들을 만들어 구현해둔 트리입니다. 쉽게 말하자면 제일 밑 노드들은 값들, 그 위에 부모 노드들에는 값들의 정보(보통 노드의 부분합)를 모아둔 트리! 예시를 보시는게 좋을 것입니다. 언제 쓰이는가? 👀 인덱스 트리는 언제 쓰일까요? 1. 부분합을 계속해서 구해야할 때, 2. 특정 인덱스의 변경 또한 계속 일어날 수 있을 때 이 두 조건이 만족할 때 주로 쓰입니다! * left - right = N 이라 가정 보통 구간 left ~ right 부분합을 구한다는 것은 left 부터 right 까지를 전부 더해야 하기에 O(N) 의 시간복잡도를 가집니다. 그래서 우리는 누적합 배열을 쓰죠! 누적합 배열에서 누적합..