[일반] 세그먼트트리,펜윅트리 뭐가 더 낳음?

[ㄴ(220.84)]

영차영차 낳고싶지만, 질문이 더 중요하니

저 둘다 써도 되는문제가 많은거같은데
둘중 뭐가 나음?

그리고, 둘중 하나밖에 못쓰는 문제도 있어?

[d(1.230)]

펜윅트리는 구현이 간편하고 빠른대신, sum query들만 보통 처리할 수 있음

[d(1.230)]

세그먼트 트리의 특수한 경우가 펜윅이라 보면 될듯

[익명(175.214)]

펜윅으로 풀리는 문제는 세그먼트로 풀수있고 그 반대는 안됨

[익명(175.214)]

펜윅의 장점은 메모리가 N이라는것. 세그먼트는 NlogN. 나머지는 세그먼트가 훨씬 우월함.

[ㄴㄴ(175.223)]

세그먼트가 왜 메모리 nlogn임?? 걍 2n아닌가

[하루룽(ailedear)]

세그메모리 4n 아니냐

[ㄴㄴ(175.223)]

난 코포에 있는 세그먼트 트리 써서 2n인데 4n짜리도 있남

[하루룽(ailedear)]

ㄴ n=6일때 세그트리 그려보면 노드 13개로 2n 초과임

[ㄴㄴ(175.223)]

ㄴ 흠... 12개로도 충분한뎅

[하루룽(ailedear)]

https://codeforces.com/blog/entry/18051
여기서 첫그림이 내가쓰는거 두번째그림이 너가쓰는건가보네