[백준 2042번] 구간 합 구하기 c++ 풀이

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

2042번: 구간 합 구하기

 

문제 분석

제시된 배열이 있을 때, 배열의 구간합을 구하는 문제.

하지만, 1) 시간 초과가 빡세고

2) 중간에 배열을 update한 뒤에 구간합을 구해야해서 일반적으로 구할 수 있는 구간합 문제는 아니다.

 

따라서 자식의 노드의 합을 노드로 갖는 segment tree 자료구조를 이용해 풀어야한다.

이때 segment tree를 이용해 계산할 경우, 최대 트리의 높이만큼을 탐색하기 때문에 O(log(n))이 된다. 

(트리의 높이는 logn이기 때문이다.)

 

문제 풀이

세그먼트 트리는 코드 구현이 상당히 빡세다.. 나도 사실 이문제는 이 풀이를 많이 참고했다.

세그먼트 트리의 주요특징은 아래와 같다.

- 부모는 자식 노드의 합을 값으로 가진다.

- root node는 배열의 모든 요소의 합을 값으로 가진다.

 

- 왼쪽 자식은 node *2, 오른쪽 자식은 node * 2+1.

            노드의 인덱스 |    포함하는 시작 인덱스    |포함하는 마지막 인덱스   
왼쪽자식   |   node * 2  |          start        | (start + end)/2 
오른쪽자식 | node * 2 + 1 |  (start + end)/2 + 1  | end

위와 같은 트리에 대한 기본 구현 방식을 알면, 위에 첨부해놓은 사이트의 설명을 찬찬히 읽어보면 이번 문제를 구현할 수 있다.

 

 

코드

//https://www.acmicpc.net/blog/view/9
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,k,i;
long long arr[1000001], tree[4000002];
long long init(int node, int start, int end){
    if(start==end){
        return tree[node]=arr[start];
    }
    return tree[node]=init(node*2,start,(start+end)/2)+init(node*2+1,(start+end)/2+1,end);
}
long long sum(int node, int start, int end, int left, int right){
    if(start>right || end<left){
        return 0;
    }
    if(left<=start && end<=right){
        return tree[node];
    }
    // 왼쪽 : node * 2 | start | (start + end)/2 
    // 오른쪽 : node * 2 + 1 | (start + end)/2 + 1 | end
    return sum(node*2, start,(start+end)/2,left,right)+sum(node*2+1,(start+end)/2+1,end,left,right);
}
void update(int node, int start, int end,int index, long long diff){
    if(index<start || index>end) return; 
    tree[node]+=diff;
    if(start!=end){
        update(node*2, start, (start+end)/2,index,diff);
        update(node*2+1,(start+end)/2+1, end,index,diff);
    }
}

int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(i=0;i<n;i++){
        scanf("%lld",&arr[i]);
    }
    init(1,0,n-1);
    for(i=0;i<m+k;i++){
        int a;
        scanf("%d",&a);
        if(a==1){
            int b;
            long long c;
            scanf("%d %lld",&b,&c);
            long long diff=c-arr[b-1];
            arr[b-1]=c;
            update(1,0,n-1,b-1,diff);
        }
        else if(a==2){
            int b, c;
            scanf("%d %d",&b,&c);
            printf("%lld\n",sum(1,0,n-1,b-1,c-1));
        }
    }
    return 0;
}

 

 

마무리

어렵다. 배열의 개수가 1,000,000으로 long long으로 관리해줘야 해서 디테일하게 변수를 잘 관리해야한다.

세그먼트 트리에 대해 이해했는데 또 까먹을 것 같아서.. 좀 더 문제를 풀어야할 것 같다. 

그래도 묵혀둔 세그먼트 트리 문제 풀기를 해서 개운하다 XD