[질문] 형님들 세그먼트 트리 알면 인덱스 트리 몰라도 되나요?

[익명(175.196)]

인덱스 트리 쓰심?

[익명(121.184)]

구간합할때 모든 부분이 월등한데 당연히 알아야 함 구현도 훨씬 쉬운데

[익명(175.196)]

넵 알겠습니다. 이게 알고보니 그 유명한 펜윅트리였군요. 당빠 공부해야겠네요

[캐티(tae826)]

인덱스 트리랑 펜윅이랑은 다른걸텐데

[캐티(tae826)]

펜윅은 바이너리 인덱스 트리고 일반적으로 인덱스 트리는 N 을 가까운 2^n 꼴로 늘려서 바텀 업으로 올라가는 방식을 인덱스 트리라고 불렀던거 같은데,, 전자는 무조건 알아둬야 하고 후자는 걍 세그트리 응용 느낌임

[캐티(tae826)]

펜윅은 사실 하는 일만 보면 세그의 하위호환인데 시간이 압도적으로 빨라서 되게 유용함 ㅇㅇ 펜윅 아니면 시간 초과나는 문제도 요즘엔 많고 구현이 훨씬 쉬워서 알아두는게 좋아

[익명(175.196)]

https://gall.dcinside.com/mgallery/board/view/?id=ps&no=15665&page=1
넵
공부했습니다. 원리도 훨씬 간단하네요