백준 2042번 구간 합 구하기

문제 링크입니다: https://www.acmicpc.net/problem/2042

새그먼트 트리를 이용하여 푸는 문제였습니다.

종만북 코드에서는 LCA(Longest Common Ancestor)를 구하는 코드이기 때문에 http://jaimemin.tistory.com/662 코드에서 조금 수정을 해야했습니다.

주의할 점은, 반환형을 int가 아닌 long long으로 해야 AC를 받을 수 있다는 점입니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N, M, K;

 

struct segmentTree

{

        //배열의 길이

        int n;

        //각 구간의 최소치

        vector<long long> pSum;

        segmentTree(const vector<long long> &array)

        {

                 n = array.size();

                 pSum.resize(n * 4);

                 init(array, 0, n - 1, 1);

        }

        //node 노드가 array[left...right] 배열을 표현할 때

        //node를 루트로 하는 서브트리를 초기화

        long long init(const vector<long long> &array, int left, int right, int node)

        {

                 if (left == right)

                         return pSum[node] = array[left];

                

                 int mid = (left + right) / 2;

                 long long leftSubTree = init(array, left, mid, node * 2);

                 long long rightSubTree = init(array, mid + 1, right, node * 2 + 1);

 

                 return pSum[node] = leftSubTree + rightSubTree;

        }

        //node가 표현하는 범위 array[nodeLeft..nodeRight]가 주어질 때

        //이 범위와 array[left..right]의 교집합

        long long query(int left, int right, int node, int nodeLeft, int nodeRight)

        {

                 //두 구간이 겹치지 않으면 무시 됨

                 if (right < nodeLeft || nodeRight < left)

                         return 0;

                 //node가 표현하는 범위가 array[left..right]에 완전히 포함되는 경우

                 if (left <= nodeLeft && nodeRight <= right)

                         return pSum[node];

                 //양쪽 구간을 나눠서 푼 뒤 결과를 합친다

                 int mid = (nodeLeft + nodeRight) / 2;

                 return query(left, right, node * 2, nodeLeft, mid) + query(left, right, node * 2 + 1, mid + 1, nodeRight);

        }

        //query()를 외부에서 호출하기 위한 인터페이스

        long long query(int left, int right)

        {

                 return query(left - 1, right - 1, 1, 0, n - 1);

        }

        //array[index]=newValue로 바뀌었을 떄 node를 루트로 하는

        //구간 트리를 갱신

        long long update(int index, int newValue, int node, int nodeLeft, int nodeRight)

        {

                 //index가 노드가 표현하는 구간과 상관없는 경우엔 무시한다

                 if (index < nodeLeft || nodeRight < index)

                         return pSum[node];

                 //트리의 리프까지 내려온 경우

                 if (nodeLeft == nodeRight)

                         return pSum[node] = newValue;

 

                 int mid = (nodeLeft + nodeRight) / 2;

                 return pSum[node] = update(index, newValue, node * 2, nodeLeft, mid) + update(index, newValue, node * 2 + 1, mid + 1, nodeRight);

        }

        //update()를 외부에서 호출하기 위한 인터페이스

        long long update(int index, int newValue)

        {

                 return update(index - 1, newValue, 1, 0, n - 1);

        }

};

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N >> M >> K;

 

        vector<long long> v;

        for (int i = 0; i < N; i++)

        {

                 int temp;

                 cin >> temp;

 

                 v.push_back(temp);

        }

 

        segmentTree seg(v);

 

        for (int i = 0; i < M + K; i++)

        {

                 int a, b, c;

                 cin >> a >> b >> c;

 

                 if (a == 1)

                         seg.update(b, c);

                 else

                         cout << seg.query(b, c) << endl;

        }

       

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]