Sqrt Decomposition 구간 쿼리를 Segment Tree를 이용해서 처리하면 시간복잡도가 $O(logN)$이다. 이는 트리의 깊이에 비례하는데, 각 노드의 자식 노드의 수를 밑으로 가지는 로그의 시간복잡도를 가지는 것이다. 예를 들어 세그먼트 트리는 자식 노드가 2개이므로 엄밀한 시간복잡도 식은 $f(x) = log_{2}(x)$이다. 그렇다면 다음과 같이 생각할 수 있다. "만약 세그먼트 트리의 자식 노드의 개수가 3개라면 시간복잡도는 어떻게 될까? 그러면 트리의 높이가 log_3(N)이므로 시간복잡도 식도 이와 같을 것이다. 그러면 공간복잡도를 배제하고 생각해보자. 시간복잡도를 최적화하려면 트리에서 자식 노드의 개수가 많을수록 유리할 것이다.하지만 우리는 마냥 공간복잡도를 배제..
