ksjb2897   1년 전

이 문제 정말 어렵네요 ㅠㅠ

세그먼트 트리로 풀다가 생각해보니 구간을 한꺼번에 업데이트 해야 할 필요성을 느꼈습니다. 근데 아무리 해도 시간복잡도가 넘쳐나서, 인터넷에 구간업데이트 할 수 있냐 물어봤는데 lazy propagation을 쓰면 할 수 있다는 군요. 그래서 그거 공부하고 시도해봤는데, 단순히 구간합 세그먼트 트리가 아니고 구간 안에서 노드별로 합해야 하는 수가 달라서 lazy propagation을 구현할 수 있는게 맞나..? 라는 생각이 들었어요.

질문 1. 세그먼트 트리에서 구간 업데이트를 구현해야 하는가?

질문 2. 만약 구간 업데이트가 필요하다면 lazy propagation이 필요한가? 아니면 다른 방법으로 구간 업데이트를 해야하는가?

너무 구체적인 방법 힌트 말고 lazy가 필요한지 구간 업데이트가 필요한지 위주로 답변해주시면 정말 감사하겠습니다 ㅠㅠ

taiga   1년 전

간단히 답해드리면,

1. 맞습니다.

2. 자식에게 값을 물려주지 않는 구현이 가능하기에 lazy없이도 풀 수 있습니다.

ksjb2897   1년 전

감사합니다..! 정보 도움 얻어서 한번 다시 풀어보겠습니다!!

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