세그먼트 트리로 풀다가 생각해보니 구간을 한꺼번에 업데이트 해야 할 필요성을 느꼈습니다. 근데 아무리 해도 시간복잡도가 넘쳐나서, 인터넷에 구간업데이트 할 수 있냐 물어봤는데 lazy propagation을 쓰면 할 수 있다는 군요. 그래서 그거 공부하고 시도해봤는데, 단순히 구간합 세그먼트 트리가 아니고 구간 안에서 노드별로 합해야 하는 수가 달라서 lazy propagation을 구현할 수 있는게 맞나..? 라는 생각이 들었어요.
질문 1. 세그먼트 트리에서 구간 업데이트를 구현해야 하는가?
질문 2. 만약 구간 업데이트가 필요하다면 lazy propagation이 필요한가? 아니면 다른 방법으로 구간 업데이트를 해야하는가?
너무 구체적인 방법 힌트 말고 lazy가 필요한지 구간 업데이트가 필요한지 위주로 답변해주시면 정말 감사하겠습니다 ㅠㅠ
ksjb2897 1년 전
이 문제 정말 어렵네요 ㅠㅠ
세그먼트 트리로 풀다가 생각해보니 구간을 한꺼번에 업데이트 해야 할 필요성을 느꼈습니다. 근데 아무리 해도 시간복잡도가 넘쳐나서, 인터넷에 구간업데이트 할 수 있냐 물어봤는데 lazy propagation을 쓰면 할 수 있다는 군요. 그래서 그거 공부하고 시도해봤는데, 단순히 구간합 세그먼트 트리가 아니고 구간 안에서 노드별로 합해야 하는 수가 달라서 lazy propagation을 구현할 수 있는게 맞나..? 라는 생각이 들었어요.
질문 1. 세그먼트 트리에서 구간 업데이트를 구현해야 하는가?
질문 2. 만약 구간 업데이트가 필요하다면 lazy propagation이 필요한가? 아니면 다른 방법으로 구간 업데이트를 해야하는가?
너무 구체적인 방법 힌트 말고 lazy가 필요한지 구간 업데이트가 필요한지 위주로 답변해주시면 정말 감사하겠습니다 ㅠㅠ