input output 5 2 2 1 2 3 4 5 1 3 6 2 2 5 1 5 2 2 3 5 17 12 해당 문제는 배열의 인덱스 요소에서 설정한 범위내에 구간의 합을 구하는 문제이다. 일반적인 배열의 구간 합은 O(n)의 시간 복잡도를 가지만 해당 문제에서 입력으로 주어지는 모든 수는 -2^63 보다 크거나 같고 2^63 - 1보다 작거나 같은 정수이므로 시간 제한이 2초이므로 보다 빠른 알고리즘을 사용해야 한다. 필자는 세그먼트 트리를 통해 해결하였는데, 세그먼트 트리는 O(logn)의 상당히 빠른 알고리즘이다. 세그먼트 트리는 몰랐던 자료구조 이기 때문에 세그먼트 트리가 무엇인지 알아보면서 풀이를 진행하겠다. 세그먼트 트리는 이진 트리 구조이다. 따라서 각 노드에 대한 정보를 알 수 있다. 부모노..