땡글이LAB

세그먼트 트리(Segment Tree)는 제목에 적힌 것처럼 이진 트리에서 응용된 트리이다. 세그먼트 트리는 여러 개의 데이터가 순서를 가지고 존재할 때, 특정 범위의 합을 구할 때 사용된다. 물론 데이터의 변경이 없다면 특정 범위의 합을 구하는 문제에서 동적 프로그래밍(DP)를 사용해도 괜찮다. 만약 주어진 데이터의 숫자가 지속적으로 변경되고 여러 번 특정 구간에 대해 합을 구해야 한다면 동적 프로그래밍(DP)의 사용이 적절할까?? 아니다. 데이터가 여러 번 바뀌고 구간 합을 여러 번 구해야 하는 상황이라면 동적 프로그래밍(DP)는 데이터가 바뀔 때마다 O(N) 시간복잡도를 가질 것이고, 데이터가 변경되는 횟수가 M이라면 총 O(NM)의 시간복잡도를 가진다. 그렇다면 세그먼트 트리의 경우는 어떨까? 세..