Data Structure1 Segment Tree Motivation segment tree 자료구조는 아래의 문제를 해결하는데 사용된다. 1. 1차원 배열의 i번째 수부터 j번째 수까지의 연속 합을 구해야할 때 (총 $m$번) 2. 배열의 i번째 수가 변경되는 쿼리를 같이 처리해야할 때 (총 $k$번) 1번의 문제만 해결해야한다면, 부분 합 (Prefix Sum) 문제로 치환하여, $O(n+m)$의 시간 복잡도로 해결할 수 있다. 하지만, 2번의 문제까지 추가가 된다면 상황이 복잡해진다. 부분 합을 이미 구해 놓은 상태에서, i번째 수가 변경된다면 부분 합을 다시 업데이트해야한다. 즉, $k$번만큼 배열의 수가 변경될때마다 부분 합을 업데이트해야하므로 여기서 $O(nk)$의 시간 복잡도가 발생한다. 여기에 m개의 연속 합을 구해야하므로 최종 시간 복잡.. 2022. 3. 19. 이전 1 다음
