백준 누적합 11659

[baekjoon 11659] 구간 합 구하기 4 (누적합) (C++)

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 기본적인 누적합 문제이다. 누적합 문제를 최근에 안 풀었더니 투 포인터로 접근했다가 시간 초과가 났다. 입력을 받으면서 앞의 인덱스의 누적 합을 따로 저장해준다. 그러면 start와 end의 구간 합을 sum[end] - sum[start-1]의 식으로 O(1)에 구할 수 있다. 여기에 쿼리가 추가되어 값이 수정되면서 구간 결과을 구하려면 세그먼트 트리 문제로 된다. 수많은..