p_ce1052   3년 전

블로그보면서 원리만 이해하고 직접 짜보려고 했는데 전파가 제대로 안일어나네요 left~right까지의 범위에 특정 수를 더하라고 했으면 어떤 노드가 이 범위 안에 완전히 속하면 lazy값만 넣어두고 나중에 query_sum에서 이 노드를 방문할때 lazy값을 반영하고 자식들한테 옮기면 된다고 생각했는데 어디가 문제일까요?

ha_ram   3년 전

add함수에서 범위에 걸쳐있는 노드일때 propagation 해줘야합니다.

p_ce1052   3년 전

범위에 걸쳐있을때는 다시 노드를 반으로 나눠서 add함수를 양쪽 구간에 호출하는데 이러면 포함될때까지 쪼개지는 것 아닌가요? 포함되면 propagation이 되구요. 걸쳐있을 때 굳이 propagation을 해줘야 하는게 이해가 잘 가지 않습니다.

ha_ram   3년 전

만약 구하려는 구간이 6~9이고

현재 구간이 5~8라고 가정하고, 현재 구간의 lazy가 2가 있다고 가정해보면

현재 구간이 구하려는 구간에 걸쳐있으므로 지금코드에서는 lazy가 전파 안되고 그냥 5~6, 7~8로 밑으로 내려갑니다.

5~6과 7~8에는 lazy가 없으므로 틀린값이 됩니다.

즉 하고싶은 말은 구간이 걸쳐있다는것은 구하려는 부분이 그 구간안에 있다는 것이므로 lazy가 남아있으면 propagation해줘야합니다.

p_ce1052   3년 전

밑으로 내려가서 둘로쪼개지던 넷으로쪼개지던 포함되는 순간에 lazy값이 생겨서 propagation되고 노드의 값을 갱신한 다음에 tree[node] = tree[node*2]+tree[node*2+1] 로 다시 올라오면서 걸쳐있는 구간까지 바뀐다고 생각했는데 51번줄이 하는일이 없는건가요 ?

p_ce1052   3년 전

propagate를 add시작할때 넣어주니까 해결되긴 했습니다. 말씀해주신부분은 고민해보겠습니다. 봐주셔서 감사합니다

ha_ram   3년 전

아 문제점을 찾았네요. 제가 위에서 말한것들은 문제 없습니다.

다른곳에 문제가 있었네요 ㄷㄷ..

42번째 줄에 관련없는 노드일때 그냥 return 해서 틀리는것같습니다.

만약 관련없는 노드의 lazy가 있다면 위로 올라가서 51번째 줄이 일을할 때

lazy가 반영이 안된채로 더해지기 때문에 tree값이 틀린값이 저장되겠네요.

잘못된 정보 드려서 죄송합니다 ㅎㅎ;;

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