segment tree

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
void init(vector<int> &tree, vector<int> &a, int node, int start, int end) {
    if (start == end) {
        tree[node] = a[start];
    } else {
        init(tree, a, node*2, start, (start+end)/2);
        init(tree, a, node*2+1, (start+end)/2+1, end);
        tree[node] = min(tree[node*2],tree[node*2+1]);
    }
}
int query(vector<int> &tree, int node, int start, int end, int i, int j) {
    if (i > end || j < start) {
        return -1;
    }
    if (i <= start && end <= j) {
        return tree[node];
    }
    int m1 = query(tree,2*node, start, (start+end)/2, i, j);
    int m2 = query(tree, 2*node+1, (start+end)/2+1, end, i, j);
    if (m1 == -1) {
        return m2;
    } else if (m2 == -1) {
        return m1;
    } else {
        return min(m1, m2);
    }
}
void update(vector<int> &tree, int node, int start, int end, int index, int value) {
    if (index < start || end < index) return;
    if (start == end) {
        tree[node] = value;
        return;
    }
    update(tree, node*2, start, (start+end)/2, index, value);
    update(tree, node*2+1, (start+end)/2+1, end, index, value);
    tree[node] = min(tree[node*2], tree[node*2+1]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n;
    vector<int> a(n+1);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
    vector<int> tree(tree_size);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    cin >> m;
    init(tree, a, 1, 1, n);
    while (m--) {
        int what;
        cin >> what;
        if (what == 1) {
            int index, value;
            cin >> index >> value;
            update(tree, 1, 1, n, index, value);
        } else {
            int start, end;
            cin >> start >> end;
            cout << query(tree, 1, 1, n, start, end) << '\n';
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
typedef long long ll;
 
using namespace std;
 
int n,m,k,t2,t3;
vector<ll> a;
vector<ll> seg;
 
long long init(int node, int start , int end){
    if(start == end)
        return seg[node] = a[start];
    int mid = (start+end)/2;
    return seg[node] = init(node*2,start,mid)+init(node*2+1,mid+1,end);
}
 
long long sum(int start , int end , int node ,int left , int right){
    if(start > right || end< left)return 0;
    if(start >=left && end<=right)return seg[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 node , int x,int y, int index , long long diff){ //x,y는 index가 포함되는지 안되는지 위치 , index = 바뀌는 index
    if(index <x || index > y) return;
    seg[node] += diff;
    if(x!= y){
        int mid = (x+y)/2;
        update(node*2, x, mid, index, diff);
        update(node*2+1 , mid+1 , y , index , diff);
    }
}
int main(){
    scanf("%d %d %d" , &n , &m ,&k);
    a.resize(n+2);
    seg.resize(4*n);
    
    for(int i=1;i<=n;i++){
        scanf("%lld" , &a[i]);
    }
    init(1,1,n);
    int t1,t2,t3;
    m+=k;
    while(m--){
        scanf("%d" , &t1);
        if(t1 == 1){
            scanf("%d %d" , &t2 , &t3);
            long long diff = t3 - a[t2];
            a[t2] = t3;
            update(1,1,n,t2,diff);
        }else if(t1 == 2){
            scanf("%d %d" , &t2 , &t3);
            printf("%lld\n" , sum(1,n,1,t2,t3));
        }
    }
    return 0;
}
 

int minupdate(int pos, int val, int node, int x, int y)

{

    if (pos<x || pos>y)

        return segMin[node];

    if (x == y)

        return segMin[node] = val;

    int mid = (x + y) / 2;

    int lcv = minupdate(pos, val, node * 2, x, mid);

    int rcv = minupdate(pos, val, node * 2 + 1, mid + 1, y);

    return segMin[node] = min(lcv, rcv);

}

맨처음 init 대신에 update로 한번에 모든걸 해결하는게 깔끔하다 

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

        {

            minupdate(i, i, 1, 0, n - 1);

        }

이런식