세그먼트 트리

가. 세그먼트 트리 a. 무엇인가 - 어떤 배열의 구간합을 트리형태로 저장 b. 특징 - 배열로 구간합을 저장하고 (S[i]= S[i-1]+A[i]) 원하는 구간을 (S[R] - S[L-1])의 형태로 구현이 가능[O(1)] - 하지만 배열의 값이 바뀌는 경우 바뀔때마다 구간합을 더해서 저장해야한다 O(N*변경) - 세그먼트 트리는 이를 O(logN)으로 만들어 줄 수 있다. 나. 구현 a. DFS 및 이분탐색의 활용 - node는 1번부터 시작하며 node*2가 왼쪽 자식노드 node*2+1이 오른쪽자식 노드가 된다. - 트리의 구성은 이분탐색으로 쭉쭉 내려가면서 start랑 end가 같아질때 해당 노드번호에 요소를 저장한다. - 리프에 저장이 끝나면 위로 돌아와서 해당구간을 더한 값을 저장해준다. p..