vc0612   6년 전

펜윅트리는 항상 세그먼트트리를 대체 할 수 있나요??

펜윅트리가 세그먼트 트리보다 코드도 더 짧고 메모리도 덜 잡아먹는데, 세그먼트 트리가 더 많이 보이는듯한(??) 건 기분탓이려나요..??


쨋ㅅ든.. 펜윅트리는 항상 세그먼트 트리를 대체할 수 있는지 궁금합니다.

혹시 그렇지 않다면, 어떤 상황에선 펜윅을 쓰지 못하고 세그먼트만 쓸 수 있는지 궁금합니다.

onjo0127   6년 전

대표적으로 일반적인 경우에 최대값/최소값 쿼리 같은 건 펜윅 트리로 처리하지 못합니다.
fenwick(i) - fenwick(j-1) 같은 형태로 나타내지 못한다면 펜윅 트리는 못 쓰신다고 보면 될 것 같아요!

vc0612   6년 전

아하 그렇군요 - ! 감사합니다..! 

댓글을 작성하려면 로그인해야 합니다.