caralho segmentado

#include <bits/stdc++.h>
#define N 100007
#pragma GCC optimize ("O3")

#pragma GCC target ("sse4")

using namespace std;

int tree[2*N], A[N], viagens, casa;

void build(int node, int start, int end){
    if(start == end) tree[node] = A[start];
    else{
        int mid = (start+end)/2;
        build(2*node, start, mid);
        build(2*node+1, mid+1, end);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
}

void update(int node, int start, int end, int idx, int val){
    if(start==end){
        A[idx] = val;
        tree[node] = val;
    }else{
        int mid = (start+end)/2;
        if(start <= idx && idx <= mid) update(2*node, start, mid, idx, val);
        else update(2*node+1, mid+1, end, idx, val);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }
}

int query(int node, int start, int end, int l, int r){
    if(end < l || r < start) return 0;

    if(l <= start && end <= r) return tree[node];
    int mid = (start+end)/2;
    return max(query(2*node, start, mid, l, r), query(2*node+1, mid+1, end, l, r));
}

int main(){
    ios_base::sync_with_stdio(false);
    int cases;
    cin >> cases;
    for(int x = 0; x < cases; x++){

        cin >> viagens >> casa;
        for(int i = 1; i <= viagens; i++) cin >> A[i];
        build(1,1, viagens);
        int c;
        cout << "Testcase " << x << ":\n";
        cin >> c;
        while(c--){
            char p;
            cin >> p;
            if(p == 'A') {
                int red; cin >> red;
                casa += red;
            }else if(p == 'B'){
                int idx, val; cin >> idx >> val;
                update(1,1,viagens, idx+1, val);
            }else{
                int l, r; cin >> l >> r;
                cout << abs(casa-query(1,1,viagens, l+1, r+1)) << endl;
            }
        }
        cout << endl;
    }
    return 0;
}