L.O.K

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ◎ 문제풀이 https://lordofkangs.tistory.com/429 [Algorithm] Lazy Propagation( 지연전파 ) ( + BOJ10999 ) With JAVA https://lordofkangs.tistory.com/411 [Alogorithm] 세그먼트 트리( Segment Tree ) 구간합 구하기 ..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ◎문제풀이 [Alogorithm] 세그먼트 트리( Segment Tree ) 구간합 구하기 ( + BOJ2042 ) With Python,JAVA [Alogorithm] 세그먼트 트리 ( Segment Tree ) 프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고..

◎ 문제 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ◎ 문제풀이 구간합을 구하는 문제이다. 시간제한이 1초이다. 대략 연산횟수 1억~10억이 1초가 걸린다. 반복문을 이용하면 시간복잡도는 O(N)이다. N은 최대 크기는 10만이다. 구간합을 M번 구해야 한다. 고로 N x M 연산해야 한다. 시간복잡도는 O(NM)이다. M도 10만이 최대이므로 최대 100억번의 연산을 수행해야 한다. 반복문을 활용하면 시간제한에 걸린다. 그러니 prefix-sum 알고리즘을 활용해보자. prefi..