[백준 2042] 구간 합 구하기 (C++)

문제 링크: www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

1. 주의할 점

- 세그먼트 트리에 대해 알고 있어야 한다

 

2. 구현

- Arr[] 배열을 통해 입력받는 수들을 저장한다(Index: 0~Num-1)

- ceil(log2(Num))을 통해 Height을 구한다. Tree[] 배열을 만들 경우, Num보다 크거나 같은 2의 제곱수 중 가장 작은 제곱수*2만큼의 공간이 필요하기 때문이다.

- Tree[] 배열의 크기를 동적으로 할당해준다(height*2 → (1<<height+1))

- Init() 함수를 통해 Tree배열을 초기화해주며, Node는 1로 설정하여 Tree의 1부터 값을 집어넣는다. 참조할 Arr[]의 범위를 start, end로 설정한다(0~Num-1)

- Sum() 함수를 통해 Arr[Left]~Arr[Right]까지의 합을 구한다

- Update() 함수를 통해 Arr[idx] → Arr[idx]+Diff만큼 바꾼다고 할 때, Tree[]의 start~end인덱스에 idx가 포함되어 있다면 +=Diff를 수행한다

 

#include <iostream>
#include <cmath>
using namespace std;
long long *tree;
long long arr[1000001];

long long init(int node, int start, int end){
    if(start==end) return tree[node] = arr[start];
    int mid = (start+end)/2;
    return tree[node] = init(2*node,start,mid)+init(2*node+1,mid+1,end);
}

long long sum(int node, int start, int end, 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 sum(node*2,start,mid,left,right) + sum(node*2+1,mid+1,end,left,right);
}

void update(int node, int start, int end, int idx, long long diff){
    if(idx<start || idx>end) return;
    tree[node]+=diff;
    if(start==end) return;
    int mid = (start+end)/2;
    update(node*2,start,mid,idx,diff);
    update(node*2+1,mid+1,end,idx,diff);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,m,k,a,b;
    long long c;
    cin>>num>>m>>k;
    int height = ceil(log2(num));
    tree = new long long[1<<(height+1)];
    for(int i=0;i<num;i++)
        cin>>arr[i];
    init(1,0,num-1);
    
    for(int i=0;i<m+k;i++){
        cin>>a>>b>>c;
        if(a==1){   //b->c로 변환
            long long diff = c-arr[b-1];
            arr[b-1]=c;
            update(1,0,num-1,b-1,diff);
        }
        else if(a==2)      //b~c합
            cout << sum(1,0,num-1,b-1,c-1)<<'\n';
    }
    return 0;
}