https://www.acmicpc.net/problem/2042제목만 보면 부분합 알고리즘을 사용할 것 같지만 어떻게 보면 비슷한 세그먼트 트리 기본 문제입니다.세그먼트 트리는 부분합과 비슷한 부분이 있습니다. 바로 부분의 값을 미리 계산해 놓고 필요할 때 적은 계산만으로 값을 도출하는 방법이라는 점 입니다. 다만 세그먼트 트리는 중간에 수를 바꾸는 등의 작업도 보다 빠르게 할 수 있어 좀 더 유연하게 사용할 수 있다는 장점이 있습니다. 기초 세그먼트 트리는 모습은 이진트리와 유사하며 각 노드는 해당하는 범위의 합 / 곱 등 사용자가 원하는 선형 계산의 값을 보유합니다. 또 각 노드의 자식 노드의 범위는 부모 노드의 범위의 절반씩에 해당합니다.또한 세그먼트 트리의 루트 노드는 1 로 설정하는 편이 편합..
