작심 24/7

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 그냥 cin cout 쓰면 무조건 시간 초과 난다. ios_base::sync_with_stdio(false); cin.tie(NULL); 를 적어주거나 scanf printf를 써야 한다. DP와 세그먼트 트리, 두 가지 방식으로 풀어 보았다. 1. DP i번째 칸에 1번째 수부터 i번째 수까지 더한 값을 저장해놓고 a부터 b까지의 합을 출력할 때는 b번째 값에서 a - 1번째 값을 빼서 출력한다. #incl..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 일반적인 방법으로 구간의 합을 구하면 O(N)이지만 이 문제에서는 시간 초과가 걸릴 가능성이 아주 높기 때문에 O(logN)인 세그먼트 트리를 이용하여 구해야 한다. 일차원 배열을 이용하여 이진 트리를 만드는 데 계산을 편하게 하기 위해서 루트를 인덱스 1로 잡고 왼쪽 노드는 부모 노드 * 2, 오른쪽 노드는 부모 노드 * 2 + 1 의 형태로 지정한다. 루트 노드를 반으로 나누어 구간 A, 구간 B..