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

세그먼트 트리 학습

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<ll> tree;
        
        void update(int node, int start, int end, int idx, ll val)
        {
            if(idx<start || end<idx) return;
            if(start == end){
                tree[node] = val;
                return;
            }

            int mid = start+end>>1;
            update(node*2, start, mid, idx, val);
            update(node*2+1, mid+1, end, idx, val);

            tree[node] = tree[2*node]+tree[2*node+1];
        }

        ll qry(int node, int start, int end, int left, int right)
        {
            if(right<start || end<left) return 0;
            if(left <= start && end <= right) return tree[node];

            int mid = start+end>>1;
            ll l = qry(2*node, start, mid, left, right);
            ll r = qry(2*node+1, mid+1, end, left, right);

            return l+r;
        }

    public:
        void init(int n)
        {
            this->n = n;
            tree.clear();
            tree.resize(4*n+1);
        }

        void update(int idx, ll val) { update(1, 1, n, idx, val); }
        ll qry(int l, int r) { return qry(1, 1, n, l, r); }
};

int n, m, k;

signed main()
{
    FASTIO;
    Seg seg;
    
    cin >> n >> m >> k;
    seg.init(n);
    for(int i = 1; i<=n; i++){
        ll a; cin >> a;
        seg.update(i, a);
    }

    for(int i = 0; i<m+k; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        if(a == 1) seg.update(b, c);
        else cout << seg.qry(b, c) << '\\n';
    }

    return 0;
}