Segment Tree and Lazy Propagation
a번째 수 부터 b번째 수 까지의 합 구하기 7개의 수 1, 10, 3, 6, 5, 6, 4가 있을 때 a번째 수 부터 b번째 수 까지의 합을 구하는 상황을 생각해봅시다. 2번째 수 부터 4번째 수 까지의 합을 구하라는 질의가 들어오면 10+3+6 = 19 2번째 수 부터 7번째 수 까지의 합을 구하라는 질의가 들어오면 10+3+6+5+6+4 = 34 처럼 a번째 수에서 b번째 수까지를 순회하면서 합을 구하면 됩니다. 이와 같은 방법으로 a번째 수 부터 b번째 수까지의 합을 구하면 숫자의 개수가 N개, 질의의 개수가 M개일 때 M개의 질의 각각에 대해 최대 N번 순회해야하므로 시간복잡도는 O(NM)이 됩니다. 이 보다 더 빠르게 할 수 있을까요? 다음과 같이 배열을 sum을 정의합시다. sum[i] = ..
알고리즘
2015. 11. 22. 15:11
최근에 달린 댓글
- Total
- Today
- Yesterday