[C/C++] 백준 #2268 수들의 합 7(세그먼트 트리)

백준에 유달리 세그먼트 트리를 이용한 문제가 많습니다.  한동안 난이도는 플래티넘 등급이었는데, 이제는 골드 등급으로 설정되어 있습니다.  그만큼 보편화된 알고리즘이라고 생각하시면 될 듯 합니다.

 

sum of sequences (with modification some numbers)

 

문제의 링크입니다.

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

2268번: 수들의 합 7

 

세그먼트 트리는 쿼리가 2종류(읽기 쿼리, 쓰기 쿼리) 이상이 존재하며, 쿼리의 수가 많을 때 사용합니다.  읽기 쿼리와 쓰기 쿼리는 서로 반대되는 개념을 가지고 있기 때문에 타협하여 \(O(M \log N)\) 알고리즘으로 동작하도록 합니다.

 

세그먼트 트리 관련한 내용들은 이미 이전 게시물 등에 소개하였으므로, 링크로 설명을 대신합니다.

https://sdev.tistory.com/512

[C/C++] 백준 #1275 커피숍2(세그먼트 트리)

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2268 - Sum of Sequences
//        - by Aubrey Choi
//        - created at 2020-01-30
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

//    Segment tree
long long tree[1<<21];
class SegmentTree
{
public:
    long long update(int c, int s, int e, int idx, int x)
    {
        if(e<=idx||s>idx) return tree[c];
        if(s+1==e) return tree[c]=x;
        int m = (s+e)/2;
        return tree[c] = update(c*2,s,m,idx,x)+update(c*2+1,m,e,idx,x);
    }
    long long sum(int c, int s, int e, int sc, int ec)
    {
        if(ec<=s||sc>=e) return 0;
        if(sc<=s&&e<=ec) return tree[c];
        int m = (s+e)/2;
        return sum(c*2,s,m,sc,ec)+sum(c*2+1,m,e,sc,ec);
    }
};

int main()
{
    int n, m, a, b, c;
    SegmentTree tree;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==1) tree.update(1,0,n,b-1,c); 
        else { if(b>c){a=b;b=c;c=a;} printf("%lld\n",tree.sum(1,0,n,b-1,c)); }
    }
}