(C++) - 백준(BOJ) 2268번 : 수들의 합

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

2268번: 수들의 합

기본 segment tree였습니다.

 

 

풀이방법

 1. 기본적으로 data n개에 대해 segment tree를 만드는데 필요한 공간은 n보다 크면서 가장 가까운 제곱수 * 2입니다. 제곱수를 찾기 귀찮기 때문에 n*4만큼의 공간을 할당해줍니다.

 

 2. 입력에 대해 들어있는 값을 갱신하거나 또는 구간의 합을 출력합니다.

명령어가 1인경우에는 입력받은 i,j의 범위가 오름차순이 아닐 수도 있습니다. i가 j보다 크다면 i,j를 swap해줍니다.

명령어가 0인경우에는 tree의 구간합들의 갱신이 필요합니다. i번째 값을 j라는 수로 갱신하고 싶다면 i를 포함하는 index들의 구간합들이 모두 갱신되어야합니다. 이들은 바꾸려는 값 j - a[i]만큼 더함으로써 수행할 수 있습니다. 그리고 해당 값으로 바뀐것이 최신이므로 tree배열이 아닌 기존 a배열의 i번째 index의 값 또한 j로 저장합니다.

 

 

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
ll n, m, tree[4000005], a[1000005];


ll sum(int start, int end, int node, int left, int right){
    if(right < start || end < left ) return 0;
    if(left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

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

int main(){
    fastio;
    cin >> n >> m;
    while(m--) {
        ll op, i, j;
        cin >> op >> i >> j;
        if(!op) {
            if (i > j) swap(i,j);
            cout << sum(1,n,1,i,j) << '\n';
        }
        else {
            ll diff = j - a[i];
            a[i] = j;
            update(1,n,1,i,diff);
        }
    }
}