rdd6584   3년 전

혹시 세그먼트트리로는 풀기 힘든데, 펜윅트리로는 쉽게 풀 수 있는 문제가 있을까요?

있다면 예시로는 어떤것이 있을까요?


혹은 그 역인, 펜윅트리로는 풀기 힘든데, 세그먼트 트리로는 쉬운게 있나요?

chogahui05   3년 전

이전에 어느 분이 질문하신 거 같더라고요.

https://www.acmicpc.net/board/...

https://discuss.codechef.com/q...


저 또한 자세히 생각해 본 적은 없는지라.. (보통 팬윅으로 풀리는 문제를 세그 트리로 풀다 보니..)

링크로만 대체할게요..

ho94949   3년 전

사실 Fenwick tree로도 RMQ를 만들수 있습니다.

http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

정말 top-down segment tree로 풀리는 문제라고 한다면 lazy propagation이 있을것 같네요

rdd6584   3년 전

두분 다 좋은 답변이 됐습니다. 감사합니다!

펜윅트리로

https://www.acmicpc.net/proble... lazy propagetion 이 문제랑

https://www.acmicpc.net/proble... RMQ

이 문제들 도전해보고 와야겠네요.

풀어보고 안되면 세그먼트트리의 장인이 되야겠어요.



사실 펜윅트리를 방금 배웠는데 사용이 조금 어려워서, 안써도 되는 구실을 찾고 있었어요. ㅎㅎ

jason9319   3년 전

조금 어려운 문제긴 하지만

https://www.acmicpc.net/board/...

과 같은 경우 BIT만 통과해요 ㅠㅠ

chogahui05   3년 전

상수가 중요하면서 팬윅이 아슬아슬하게 통과하는 경우에는

팬윅을 써야겠군요.. 간혹 가다가 통과할 만한 복잡도인데.. TLE가 나는 경우도 있었던 거 같긴 하네요.

rdd6584   3년 전

그런 경우도 있군요 ! ㅠㅠ 결국에는 두 자료구조에 모두 충실해야겠네요 답변 감사합니다.

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