hld sum interval

#include <bits/stdc++.h>
#define MAX 200007
#define INF 1e9 + 7
using namespace std;
typedef long long ll;

struct group{
    int left, mid, right, seg;
    group(int _l, int _m, int _r, int _s): left(_l), mid(_m), right(_r), seg(_s) {}
    group(){ left = right = mid = seg = 0;}
};

struct ST {

    vector<int> seg,left, right, middle, acum, ans, arr;

    void get(int id){
        right[id] = right[2*id+1];
        right[id] = max(seg[2*id+1], right[2*id+1]);
        right[id] = max(seg[2*id+1] + right[2*id], right[id]);
        right[id] = max(seg[2*id] + seg[2*id+1], right[id]);

        left[id] = left[2*id];
        left[id] = max(seg[2*id], left[2*id]);
        left[id] = max(seg[2*id] + left[2*id+1], left[id]);
        left[id] = max(seg[2*id] + seg[2*id+1], left[id]);

        middle[id] = right[2*id] + left[2*id+1];
        middle[id] = max(middle[id], right[2*id] + seg[2*id+1]);
        middle[id] = max(middle[id], seg[2*id] + left[2*id+1]);
        middle[id] = max(middle[id], seg[2*id] + seg[2*id+1]);

        seg[id] = seg[2*id] + seg[2*id+1];
        ans[id] = max(left[id], max(middle[id], right[id]));
    }
    void build(int id, int l, int r){
        if(l == r)  seg[id] = left[id] = middle[id] = right[id] = arr[l];
        else{
            int mid = (l+r)/2;
            build(2*id, l, mid);
            build(2*id+1, mid+1, r);
            get(id);
        }
    }

    ST(vector<int> a){
        arr = a;
        seg.assign(arr.size(), 0);
        acum.assign(arr.size(), INF);
        build(1, 0, arr.size()-1);
    }

    void add(int id, int l, int r, int val){
        if(val != INF) {
            acum[id] = val;
            seg[id] = left[id] = middle[id] = right[id] = val*(r-l+1);
        }
    }

    void update(int id, int l, int r, int x, int y, int v){
        if(x > r || l > y) return;
        else if(x <= l && r <= y) add(id, l, r, v);
        else{
            int mid = (l+r)/2;
            add(2*id, l, mid, acum[id]);
            add(2*id+1, mid+1, r, acum[id]);
            acum[id] = INF;

            update(2*id, l, mid, x, y, v);
            update(2*id, mid+1, r, x, y, v);
            get(id);
        }
    }

    void update(int x, int y, int val){
        if(x < 0 || y > arr.size()-1) return;
        update(1, 0, arr.size()-1, x, y, val);
    }

    group query(int id, int l, int r, int x, int y){
        if(x > r || l > y) return group(0, 0, 0, 0);
        else if(x <= l && r <= y) return group(left[id], middle[id], right[id], seg[id]);
        else{
            int mid = (l+r)/2;
            add(2*id, l, mid, acum[id]);
            add(2*id+1, mid+1, r, acum[id]);
            acum[id] = INF;

            group q1 =  query(2*id, l, mid, x, y);
            group q2 = query(2*id, mid+1, r, x, y);
            group resp;
            resp.left = q1.left;
            resp.left = max(q1.seg + q2.left, resp.left);
            resp.left = max(q1.seg + q2.seg, resp.left);

            resp.right = q2.right;
            resp.right = max(q2.seg + q1.right, resp.right);
            resp.right = max(q1.seg + q2.seg, resp.right);

            resp.mid = q1.right + q2.left;
            resp.mid = max(q1.seg + q2.seg, resp.mid);
            resp.mid = max(q1.seg + q2.left, resp.mid);
            resp.mid = max(q1.right + q2.seg, resp.mid);

            return resp;
        }
    }

    group query(int x, int y){
        if(x < 0 || y > arr.size()-1) return group(-INF, -INF, -INF, -INF);
        return query(1, 0, arr.size()-1, x, y);
    }
};

vector<int> arr;
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        arr.push_back(x);
    }
    ST oi = ST(arr);
    return 0;
}