인프런 커뮤니티 질문&답변

안녕하세요 재윤님 ㅎㅎ

세그먼트 트리 문제는 모두 펜윅 트리로 해결해도 되나요?

>> 아닙니다.역원이 존재하지 않는 구간이나 lazy propagation을 예로 들 수 있습니다. 이럴 때는 세그먼트 트리로 해야 합니다. 다만 코딩테스트에는 역원이 존재하지 않는 구간이나 lazy propagation은 나오지 않으니 펜윅트리만으로도 충분히 가능합니다.

왜 역원이 존재하지 않는 구간에서는 펜윅트리가 되지 않을까요?

예를 들어 a ~ b 까지의 구간곱을 구한다고 했을 때.. 음.. 그림으로 설명하자면요.

이렇게 되는 것이죠. 그렇기 때문에 무조건 역원이 필요한데 그게 없으면 안됩니다. (근데 이런 경우가 그렇게 많지는 않습니다.)

역원이란?

역원은 참고로

a * b

=

b * a

= e(항등원)

이라고 할 때 b를 a의 역원이라고 합니다.

실수집합에 대해 덧셈을 한다고 했을 때 원소 a의 역원은 -a가 되고 곱셈연산자에 대해 a의 역원은 1 / a가 되는 것이죠. 따라서 실수에서는 곱셈에 대한 0에 대한 역원은 존재하지 않습니다. 즉 이부분은 역원이 존재하지 않는 구간입니다.

특정 구간합을 구할 경우에는 세그먼트 트리가 시간복잡도 상으로 유리할까요?

>> 시간복잡도가 아니라 공간복잡도상 조금 유리합니다. 펜윅트리는 세그먼트 트리의 변형으로 세그트리보다 메모리를 덜 쓰고(n) 부분합으로써 모든 구간합을 구할 수 있다는 것이 장점이니까요.

​

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.