SegmentTree 개념

💡 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 연산을 진행하기 위해 사용하는 자료구조 문제인식 N개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지의 합을 구하는 것은 어려운 일이 아니다. 예를 들면, 아래 배열에서 5번째에서 11번째 까지 더하는 방법은 그냥 배열을 돌면서 더하면 된다. 그 시간 복잡도는 대략 O(N) 이다. 하지만 이와 같은 a, b의 쌍이 M개 주어졌을 때는 O(M*N) 이 된다. 너무 오래 걸리니까 더 좋은 방법을 찾아보자. 구간 합을 구할 때마다 N을 전부 도는게 너무 오래 걸린다면, 특정 구간의 합을 미리 저장하고 이 값들의 합을 구해보자. 이때, 이진 트리를 활용할 수 있다. 트리 생성 구간 합을 저장해 보자. 이 전체 의 합은 66이다. 이 구간의..