[백준-11659]구간합구하기4

 

구간합을 구하는 간단한 문제였다. 세그먼트 트리 나 누적합 으로 풀면 간단하게 풀린다. 누적합 로직은 다음과 같다.

• (a~b)의 합 = b까지의 합 - (a-1)까지의 합

코드는 두가지 버전으로 작성해보았다.

// 세그먼트 트리 로직
#include <cstdio>

using namespace std;
typedef long long LL;
LL tree[300000];

LL query(int node, int s, int e, int l, int r) {
	if (e < l || r < s) return 0;
	if (l <= s && e <= r) return tree[node];
	else {
		return query(node * 2, s, (s + e) / 2, l, r) + 
			query(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
	}
}
void update(int node, int s, int e, int idx, LL v) {
	if (idx < s || e < idx) return;
	if (s == e) tree[node] = v;
	else {
		update(2 * node, s, (s + e) / 2, idx, v);
		update(2 * node + 1, (s + e) / 2 + 1, e, idx, v);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int main() {
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	LL input;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &input);
		update(1, 1, n, i, input);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		printf("%lld\n", query(1, 1, n, a, b));
	}
	return 0;
}

 

// 누적합으로 풀기
#include <cstdio>

using namespace std;
typedef long long LL;

int sum[100001];
int main() {
	int n, m, a, b;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a);
		sum[i] = sum[i - 1] + a;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", sum[b] - sum[a - 1]);
	}
	return 0;
}

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

11659번: 구간 합 구하기 4