백준 2042번 구간 합 구하기

백준 2042번 구간 합 구하기

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include <algorithm>
#include <cstring> //memset
#include<tuple>
using namespace std;
typedef long long ll;
const long long MAX = 1000000 + 2;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<int, pii> piit;
typedef pair<pii, pii> dpii;
const int INF = 87654321;
long long N, M, K;
long long seg[MAX * 4] = {};
long long arr[MAX] = {};
struct Segtree{
\
    long long query(int l, int r, int node, int nodeL, int nodeR) {
        if (nodeL>r || nodeR<l) return 0;//항등원
        if (l <= nodeL && nodeR <= r) return seg[node];
        int mid = (nodeL + nodeR) / 2;
        return (query(l, r, node * 2, nodeL, mid)+ query(l, r, node * 2 + 1, mid + 1, nodeR));
    }
    long long update(int index,int value,int node,int nodeL,int nodeR) {
        if (index<nodeL || nodeR < index) return seg[node];
        if (nodeL == nodeR) return seg[node] = value;
        int mid = (nodeL + nodeR) / 2;
        return seg[node] = (long long)update(index, value, node * 2, nodeL, mid)+ update(index, value, node * 2 + 1, mid+1, nodeR);
    }
    long long init(int l, int r, int node) {
        if (l == r) return seg[node] = arr[l];
        int mid = (l + r) / 2;
        return seg[node]=init(l, mid, node * 2)+ init(mid + 1, r, node * 2 + 1);
    }
};
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    Segtree Tree;
    for (int i = 1; i <=N; i++) {
        long long k;
        cin >> k;
        arr[i] = k;
    }
    Tree.init(1, N, 1);
    long long a, b, c;
    for (int i = 1; i <=M + K; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            Tree.update(b , c, 1, 1, N);
            continue;
        }
        
        if (a == 2) {
            long long ans = Tree.query(b, c, 1, 1, N);
            cout << ans<<endl;
            continue;
        }
        
    }
    return 0;
}

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

전형적인 세그먼트 트리 문제입니다. 

이 문제를 풀면서 알게 된점은 세그먼트 트리와는 관계가 없지만,

1.전역변수와 동적할당은 배열크기를 매우 크게 선언 할 수 있다. 벡터의 경우는 10억까지 가능

2.지역변수의 경우는 동적할당으로 크게잡을 수 있지만, 일반 1차원 배열 같은 경우는 

int 형은 100만까지 가면 터진다. 

왜 그럴까? 지역변수의 경우는 메모리 할당의 경우가 스택이므로, 오버플로우가 발생하기 때문입니다.