Tree

세그먼트 트리(2021.03.27)

목차 세그먼트 트리 어떤 수들의 집합이 있다. 그 집합은 원소가 마구마구 변할 수 있다고 한다. 이 때, 그 집합의 부분합을 아주 빠르게 구하기 위해서 만들어진 구조이다. 예를 들어서.. 1, 5, 6, 7, 4, 8, 2, 3 이렇게 수가 있다고 하자. 우리가 이 수들에서 특정 범위의 합을 구하려면 어떻게 해야할까? 역시 제일 간단한 방법은 다 더하는 것이다. 3~6번째 원소를 더하면. 6+7+4+8 = 25 이렇게 다 더하는 경우 시간복잡도는 O(N)으로 작은 범위 내에서 보면 나쁠 수 있다. 하지만, 이 합을 원하는 곳이 많아서 수천, 수만명이 요구를 한다면?? 또, 이 데이터에 접근 가능한 사람이 많아서 계속해서 값이 바뀐다면?? 참으로 난감할 것이다. 데이터는 바꿔줄 수 있지만. 합을 계속 해서..