zych1751   4달 전

세그먼트 트리로 구현했는데, update나, sum을 부를때 (1, 0, n-1, ...)으로 부르면 틀리는데, (1, 0, MAX-1, ...)으로 하면 맞았다고 나옵니다.

이게 왜 그런지 설명해주실 수 있을까요?

ntopia   4달 전

push_down 에서  temp값을 밑으로 내리기만 하고 현재 노드에는 temp값을 적용시키지 않는데요,

이게 거의 모든 경우에는 별 문제가 없는데

왜냐면 Update 함수의 밑 부분에서 tree[node] 값을 잘 갱신 시켜주니까요

그런데

Update에서 43번째 줄 조건에 걸린 경우에는

바로 return을 해버리는데, 이러면 현재 node에 걸려있던 temp값은 밑으로 내려버렸는데

그게 tree[node] 에 적용은 되지 않아서

특수한 경우에 문제가 되는 것 같습니다


이것도 사실 추측이라 맞는지 아닌지는 모르겠네요 ㅠㅠ

ntopia   4달 전

push_down 함수 고치니까 맞네요.

zych1751   4달 전

아 그렇네요 ㅠㅠ 0, MAX-1의 경우 항상 완전 이진 트리라서 리프노드가 아닌경우에는 자식의 개수가 짝수라서 push_down할때 자기자신을 갱신해줄 필요가 없는데 0, n-1로 하는경우에는 자식의 개수가 홀수인 경우가 생길수도 있어서 개수로 판단해야 하는군요.

답변 감사합니다!

덕분에 해결됬습니다.

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