Loading...
다음 개의 줄 각각에는 두 정수 이 공백으로 구분되어 주어진다.
입력 1
8 3
3 1 4 1 5 9 2 6
3 5
0 7
2 2
출력 1
15
31
4
설명: 첫 번째 질의는 위 그림의 예와 같이 . 두 번째 질의는 전체 합으로 . 세 번째 질의는 한 칸만의 합 .
입력 2
5 4
-2 3 -1 5 4
0 4
0 0
1 3
2 4
출력 2
9
-2
7
8
이 문제는 누적합 없이 풀면 한 질의에 최악 이 들어 전체 이다. 이면 이라 시간 안에 못 푼다. 누적합을 전처리하면 전체 이다.