Lazy Propagation
-
Lazy propagation알고리즘 2020. 3. 17. 18:30
사전 지식segment tree에서 하나의 값을 업데이트하는 연산의 시간복잡도는 O(logN) (N : 배열의 길이)인데, 나머지 수들도 변경해줘야하므로총 걸리는 시간복잡도은 O(NlogN)이다. 그런데, 이전에서 다룬 것 처럼 한번에 하나의 수를 업데이트 하는것이 아닐 경우의 시간 복잡도는 어떨까? 10개의 수 1, 10, 3, 6, 5, 6, 4, 2, 9, 7에 대해 3번째 수부터 6번째 수까지 5씩 더하는 업데이트해야 하는 경우을 생각해보자.이전 포스팅에서 사용한 업데이트 방식을 사용하면 업데이트 함수를 3,4,5,6번째 숫자에 대해 각각 호출해야한다. 즉, 길이 N인 배열에 질의가 K번 들어올 때 (for문과 같은 반복문을 사용할 경우) 전체 업데이트에 O(NKlogN)의 시간복잡도 필요하다. ..