백준(BOJ) 11659 구간 합 구하기 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

문제 풀이에 이용된 알고리즘: 다이나믹 프로그래밍, 세그먼트 트리

 

구간 내 누적합을 구하는 문제인데, 단순히 for문을 이용하여 계산할 경우 시간 초과가 발생했던 것으로 기억한다.

 

DP를 이용하여 효율적으로 문제 풀이를 진행할 수 있는데, 최근 세그먼트 트리를 공부하기 위해서 이 문제를 다시 풀어보았다.

 

세그먼트 트리에 대한 설명은 나동빈님의 블로그(https://blog.naver.com/ndb796/221282210534)에 정말 잘 설명되어 있으니, 꼭 한 번 읽어보면 좋을 것 같다.

 

41. 세그먼트 트리(Segment Tree)

 

1. 전체 데이터 시퀀스의 구간을 절반으로 쪼개 가며 구간합을 구한 후, 트리를 구축한다.

 

2. 쿼리문을 통해서 구간 left ~ right의 누적합을 검색한다.

 

위의 두 스텝을 이용해서 이 문제를 풀 수 있다. update 함수는 필요하지 않다.

 

처음 세그먼트 트리를 구현하는 경우에는 재귀가 이용되는 만큼, 함수 작성에 있어서 자잘 자잘한 오류가 많이 발생하여 많은 시간을 소모하게 되는 것 같다.

 

/* BOJ 11659 구간 합 구하기4 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, m, arr[100001];
vector<int> tree;
 
ll make_segtree(int start, int end, int node)
{
    if (start == end) return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
    return tree[node] = make_segtree(start, mid, node * 2) + make_segtree(mid + 1, end, node * 2 + 1);
}
 
ll query(int start, int end, int node, int left, int right)
{
    // 구하려는 범위가, 노드의 구간을 벗어나는 경우
    if (left > end || right < start) return 0;
    
    // 노드의 구간이, 구하려는 범위에 포함되는 경우
    if (left <= start && end <= right) return tree[node];
 
    int mid = (start + end) / 2;
    return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
    tree.resize(n * 4);
 
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    make_segtree(1, n, 1); // 구간합 트리 생성
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << query(1, n, 1, a, b) << endl;
    }
 
    return 0;
}