세그먼트 트리에 대한 글은 이미 많습니다. 심지어 다들 구체적으로 설명해주고 계십니다. 그런데 세그먼트 트리를 단지 구간합 트리라고 알고 계시는 분들이 생각보다 많이 계신 이유로 오해를 정정하고자 포스팅해보겠습니다. 세그먼트 트리가 없다면? 세그먼트 트리(구간 트리)는 주어진 쿼리에 대해서 빠르게 응답하기 위한 자료구조입니다. 배열 A가 주어져있고 A의 start~end 구간까지의 합을 구하려고 합니다. for문으로 answer+=A[i]를 돌리면 되겠죠. 그런데 만약 이 구간내 값이 변동이 된다면 어떨까요?? 총 M번 반복한다고 가정했을때, 수정 연산(O(1))+ 합산 연산 = O(NM)의 시간복잡도가 발생합니다. 세그먼트 트리 도입 여기에 세그먼트 트리를 사용한다면 어떻게 변할까요?? 수정 연산 = ..
