Segment Tree Maximum Sum (from SPOJ) problem solution

segment_tree_max_sum.cpp

//
//  segment_tree_max_sum.cpp
//  Competitive Programming
//
//  Created by Shahed Bin Satter on 24/9/20.
//  Copyright © 2020 Shahed Bin Satter. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

const int nmax = 2e5 + 1;
pair<int,int> tree[nmax * 4];
int arr[nmax];

pair<int, int> reorder(pair<int, int> p) {
    if (p.first >= p.second) return p;
    return make_pair(p.second, p.first);
}

pair<int, int> highest(pair<int, int> ab, pair<int, int> cd) {
    if (ab.second >= cd.first) return ab;
    if (cd.second >= ab.first) return cd;
    return ab.first >= cd.first ? make_pair(ab.first, cd.first) : make_pair(cd.first, ab.first);
}

void update(int id, int left, int right, int k, int val) {
    if (left == right) {
        tree[id].first = val;
        tree[id].second = -1;
        return;
    }
    int mid = (left + right) / 2;
    if (k <= mid) {
        update(2 * id, left, mid, k, val);
    } else {
        update(2 * id + 1, mid + 1, right, k, val);
    }
    pair<int,int> l = tree[2 * id];
    pair<int, int> r = tree[2 * id + 1];
    tree[id] = highest(l, r);
}

pair<int, int> query(int id, int left, int right, int a, int b) {
    if (right < a || left > b) {
        return make_pair(-1, -1);
    }
    if (a <= left && b >= right) {
        return tree[id];
    }
    int mid = (left + right) / 2;
    pair<int, int> l = query(2 * id, left, mid, a, b);
    pair<int, int> r = query(2 * id + 1, mid + 1, right, a, b);
    
    return highest(l, r);

}

void build(int id, int left, int right) {
    if (left == right) {
        tree[id].first = arr[left];
        tree[id].second = -1;
        return;
    }
    int mid = (left + right) / 2;
    
    build(2 * id, left, mid);
    build(2 * id + 1, mid + 1, right);
    
    pair<int,int> l = reorder(tree[2 * id]);
    pair<int, int> r = reorder(tree[2 * id + 1]);
    tree[id] = highest(l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, q;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        arr[i] = input;
    }
    build(1, 1, n);
    cin >> q;
    for (int i = 0; i < q; i++) {
        char type;
        cin >> type;
        if (type == 'Q') {
            // query
            int a, b;
            cin >> a >> b;
            pair<int, int> res = query(1, 1, n, a, b);
            cout << res.first + res.second << "\n";
        } else {
            // update
            int idx, val;
            cin >> idx >> val;
            update(1, 1, n, idx, val);
        }
    }
    
    return 0;
}