Segment tree (range addition, range maximum)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;



const int inf = 1e9;
const int MAXN = 300005;

int n;
int arr[MAXN];

int st[4*MAXN];
int lazy[4*MAXN];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        st[v] = arr[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        st[v] = max(st[2*v], st[2*v+1]);
    }
}

void push(int v) {
    st[2*v] += lazy[v];
    lazy[2*v] += lazy[v];
    st[2*v+1] += lazy[v];
    lazy[2*v+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int toadd) {
    if (l > r) return;
    if (l == tl && tr == r) {
        st[v] += toadd;
        lazy[v] += toadd;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(2*v, tl, tm, l, min(r, tm), toadd);
        update(2*v+1, tm+1, tr, max(l, tm+1), r, toadd);
        st[v] = max(st[2*v], st[2*v+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return -inf;
    if (l <= tl && tr <= r) {
        return st[v];
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        return max(query(2*v, tl, tm, l, min(r, tm)),
                   query(2*v+1, tm+1, r, max(l, tm+1), r));
    }
}

void Main() {
    cout << "Enter N, the size of the array, and then N numbers\n";
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    build(1, 0, n-1);
    cout << "First type of query:\n";
    cout << "--> 1 l r\n";
    cout << "--> Get the maximum element in range [l, r]\n";
    cout << "Second type of query:\n";
    cout << "--> 2 l r v\n";
    cout << "--> Add v to elements in range [l, r]\n";
    while (true) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            cout << "max[" << l << ", " << r << "] = " << query(1, 0, n-1, l, r) << "\n";
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            update(1, 0, n-1, l, r, x);
        }
    }
}

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    #ifdef _DEBUG
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    #ifndef _DEBUG
    #endif
    Main();
}