segment tree가 뭔지 공부하고 구현해보려고 문제를 풀어보았는데, 시간초과가 나서 해결하면서 혹시 저처럼 구현하신 분들 있으시면 도움이 될 것 같아서 올립니다
제가 시간초과가 난 부분은 BinarySearchSum (구간합 구하는 함수) 인데요, 처음에는 종료조건을 if (start == numStart && end == numEnd)로만 줬었는데, if (numStart == numEnd) 일 때 (구간 길이가 1인 경우) 숫자배열 nums에서 바로 리턴해주고 종료할 수 있도록 처리해줬더니 시간 초과가 해결되었습니다. 예를 들어 index 3 - index 3 까지의 구간합을 구하게 될 때, 기존의 종료조건에서는 세그먼트 트리노드와 범위가 일치하는 리프노드까지 내려가서 리턴하도록 했는데, 새 종료조건을 추가하면서 내가 어떤 노드에 있든 바로 값을 리턴시켰습니다. 별로 중요하지 않을 거라 생각했는데 크기가 1인 구간합을 구하는 경우가 많은 듯 합니다.
shyou1119 2년 전
segment tree가 뭔지 공부하고 구현해보려고 문제를 풀어보았는데, 시간초과가 나서 해결하면서 혹시 저처럼 구현하신 분들 있으시면 도움이 될 것 같아서 올립니다
제가 시간초과가 난 부분은 BinarySearchSum (구간합 구하는 함수) 인데요, 처음에는 종료조건을 if (start == numStart && end == numEnd)로만 줬었는데, if (numStart == numEnd) 일 때 (구간 길이가 1인 경우) 숫자배열 nums에서 바로 리턴해주고 종료할 수 있도록 처리해줬더니 시간 초과가 해결되었습니다. 예를 들어 index 3 - index 3 까지의 구간합을 구하게 될 때, 기존의 종료조건에서는 세그먼트 트리노드와 범위가 일치하는 리프노드까지 내려가서 리턴하도록 했는데, 새 종료조건을 추가하면서 내가 어떤 노드에 있든 바로 값을 리턴시켰습니다. 별로 중요하지 않을 거라 생각했는데 크기가 1인 구간합을 구하는 경우가 많은 듯 합니다.