seg tree

#include <bits/stdc++.h>
#define MAX 1000007

using namespace std;

int seg[4*MAX],acum[4*MAX], arr[MAX];

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

void update(int id, int l, int r, int pos, int val){
    if(l == r) seg[id] = val;
    else{
        int mid = (l+r)/2;
        if(mid <= pos) update(2*id, l, mid);
        else update(2*id, mid+1, r);

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


void add(int id, int l, int r, int val){
    seg[id] = val*(r-l+1);
    acum[id] += val;
}
void range(int id, int l, int r, int x, int y, int val){
    if(l > y || r < x) return;
    else if(x <= l && y <= r) add(id, l, r, val);
    else{
        int mid = (l + r)/2;
        add(2*id, l, mid, acum[id]);
        add(2*id+1, mid+1, r, acum[id]);
        acum[id] = 0;
        range(2*id, l, mid, x, y, val);
        range(2*id+1, mid+1, r, x, y, val);
        seg[id] = max(seg[2*id], seg[2*id+1]);
    }
}

int query(int id, int l, int r, int x, int y){
    if(l > y || r < x) return 0;
    else if(x >= l && y <= r) return 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] = 0;
        return max(query(2*id, l, mid), query(2*id+1, mid+1, r));
    }
}
int main(){
    return 0;
}