zhoang3   4년 전

세그먼트 트리 이용해서 풀었습니다.

주석 처리한 부분은 리프노드 값을 바꾸어 부모 노드까지 값을 바꾸어 주는 코드이고
주석 아닌 부분은 부모노드부터 내려가면서 차이를 빼주는 코드로 생각했습니다.
5%에서 틀렸습니다가 나오던데... 어떤 부분이 잘 못 된 걸까요...?


djm03178   4년 전

update에서 start == end일 때는 Num[start]의 값도 바꿔주어야 올바른 답을 구할 수 있습니다.

sait2000   4년 전

입력으로 long long 범위의 수가 들어오므로 int로 받으면 안 됩니다. 그리고 Tree 사이즈가 1 작습니다. 별 상관은 없겠지만

zhoang3   4년 전

이 부분에서
start와 end 비교 전 Tree[node] += diff 를 하면
Tree[node] = Num[start] 와 같은 것 아닌가요?

리프 노드일 경우
Tree[node] : num[b] 이고
diff : c - num[b] 이니깐
Tree[node] + diff = c 이므로
값을 바꾸는 것과 같은 것 아닌가요?

djm03178   4년 전

제가 드린 예시를 넣어보셨나요? Num의 값이 안 변했기 때문에 diff를 계산할 때 마지막으로 변경한 값과의 차이가 아닌, 맨 처음 값과의 차이가 계산되기 때문에 틀립니다.

zhoang3   4년 전

해결했습니닷!!!

감사합니다 ㅎㅎ

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