백준 2268번 수들의 합

문제 링크입니다: https://www.acmicpc.net/problem/2268

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

#include <iostream>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

 

long long init(vector<long long> &tree, vector<long long> &arr, int node, int start, int end)

{

        if (start == end)

                 return tree[node] = arr[start];

        else

        {

                 int mid = (start + end) / 2;

                 return tree[node] = init(tree, arr, node * 2, start, mid) + init(tree, arr, node * 2 + 1, mid + 1, end);

        }

}

 

void update(vector<long long> &tree, int node, int start, int end, int idx, long long diff)

{

        if (!(start <= idx && idx <= end))

                 return;

 

        tree[node] += diff;

 

        if (start != end)

        {

                 long long mid = (start + end) / 2;

 

                 update(tree, node * 2, start, mid, idx, diff);

                 update(tree, node * 2 + 1, mid + 1, end, idx, diff);

        }

}

 

long long query(vector<long long> &tree, int node, int start, int end, int i, int j)

{

        if (i > end || j < start)

                 return 0;

 

        if (i <= start && end <= j)

                 return tree[node];

 

        long long mid = (start + end) / 2;

 

        return query(tree, node * 2, start, mid, i, j) + query(tree, node * 2 + 1, mid + 1, end, i, j);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        int height = (int)ceil(log2(N));

        int tree_size = 1 << (height + 1);

 

        vector<long long> arr(N + 1), tree(tree_size);

        init(tree, arr, 1, 1, N);

 

        for (int i = 0; i < M; i++)

        {

                 int op;

                 cin >> op;

 

                 //쿼리

                 if (op == 0)

                 {

                         int a, b;

                         cin >> a >> b;

 

                         if (a > b)

                                 swap(a, b);

 

                         cout << query(tree, 1, 1, N, a, b) << "\n";

                 }

                 //update

                 else

                 {

                         int idx, val;

                         cin >> idx >> val;

 

                         long long diff = val - arr[idx];

                         arr[idx] = val;

                         update(tree, 1, 1, N, idx, diff);

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~