Dynamic Segment Tree 는 다음과 같은 경우에 사용됩니다. 0으로 초기화 된 10억개의 수열이 있을 때 Q(10만)개의 질의에 대해 실시간으로 업데이트와 그에 대한 답을 구하는 경우 일반적인 세그먼트 트리로는 10억개의 공간을 모두 할당 할 수 없기 때문에 불가능 합니다. 하지만 이때 잘 생각해 보면 1번의 쿼리에 변경되는 노드의 갯수는 log2(10억) =(약)21의 갯수만 변경 되는 것을 알 수 있습니다. 따라서 최대 21 * Q(10만) 개의 공간만 있으면 가능하겠다는 아이디어에서 Dynamic Segment Tree 는 출발 합니다. 즉 다음과 같은 트리에서 2번 위치의 값이 변경이 된다면 노드의 갯수를 회색으로 색칠 된 3개만 만들어 놓겠다는 것이 Dynamic Segment Tr..
