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

 

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

기본적인 누적합 문제이다.

누적합 문제를 최근에 안 풀었더니 투 포인터로 접근했다가 시간 초과가 났다.

 

입력을 받으면서 앞의 인덱스의 누적 합을 따로 저장해준다.

그러면 start와 end의 구간 합을 sum[end] - sum[start-1]의 식으로 O(1)에 구할 수 있다.

 

여기에 쿼리가 추가되어 값이 수정되면서 구간 결과을 구하려면 세그먼트 트리 문제로 된다.

수많은 쿼리를 nLogn에 업데이트하고, 구할 수 있게 된다.

 

#include <iostream>

using namespace std;

int N, M, arr[100001], sum[100001], from, to, temp;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		temp += arr[i];
		sum[i] += temp;
	}
	for (int i = 0; i < M; i++) {
		cin >> from >> to;
		cout << sum[to] - sum[from - 1] << "\n";
	}
}