[Spoj] GSS3 - Can you answer these queries III

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : GSS3 - Can you answer these queries III
Source            : Spoj
Category          : Data Structure
Algorithm         : Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define FOR(i, n)                 for (int i = 1; i <= n; i++)
#define For(i, n)                 for (size_t i = 0; i < n; i++)
#define inf                       12345678
#define max4(a, b, c, d)          max(a, max(b, max(c, d)))
#define max5(a, b, c, d, e)       max(a, max4(b, c, d, e))
 
inline int read()                 { int a; scanf("%d", &a); return a; }
 
static const int maxn = 50000 + 5;
 
struct segmentTree
{
    int prefixMaxSum, suffixMaxSum, maxSum, sum;
    segmentTree(int prefixMaxSum = 0, int suffixMaxSum = 0, int maxSum = 0, int sum = 0)
    {
        this->prefixMaxSum = prefixMaxSum;
        this->suffixMaxSum = suffixMaxSum;
        this->maxSum = maxSum;
        this->sum = sum;
    }
    void assignLeaf(int value)
    {
        prefixMaxSum = suffixMaxSum = maxSum = sum = value;
    }
    void marge(const segmentTree &left, const segmentTree &right)
    {
        if (left.prefixMaxSum == inf)
        {
            prefixMaxSum = right.prefixMaxSum;
            suffixMaxSum = right.suffixMaxSum;
            maxSum = right.maxSum;
            sum = right.sum;
        }
        else if (right.prefixMaxSum == inf)
        {
            prefixMaxSum = left.prefixMaxSum;
            suffixMaxSum = left.suffixMaxSum;
            maxSum = left.maxSum;
            sum = left.sum;
        }
        else
        {
            sum = left.sum + right.sum;
            prefixMaxSum = max(left.prefixMaxSum, left.sum + right.prefixMaxSum);
            suffixMaxSum = max(right.suffixMaxSum, right.sum + left.suffixMaxSum);
            maxSum = max5(prefixMaxSum, suffixMaxSum, left.maxSum, right.maxSum,
                          left.suffixMaxSum + right.prefixMaxSum);
        }
    }
    int getValue()
    {
        return max4(prefixMaxSum, suffixMaxSum, maxSum, sum);
    }
} tree[maxn << 2];
 
int arr[maxn];
 
void build(int node, int a, int b)
{
    if (a > b) return;
    if (a == b)
    {
        tree[node].assignLeaf(arr[a]);
        return;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    build(left, a, mid);
    build(right, mid+1, b);
    tree[node].marge(tree[left], tree[right]);
}
 
void update(int node, int a, int b, int pos, int val)
{
    if (a > b || a > pos || b < pos) return;
    if (a >= pos && b <= pos)
    {
        tree[node].assignLeaf(val);
        return;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    update(left, a, mid, pos, val);
    update(right, mid+1, b, pos, val);
    tree[node].marge(tree[left], tree[right]);
}
 
segmentTree query(int node, int a, int b, int i, int j)
{
    if (a > b || a > j || b < i)
    {
        segmentTree nul = segmentTree(inf);
        return nul;
    }
    if (a >= i && b <= j) return tree[node];
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    segmentTree p1 = query(left, a, mid, i, j);
    segmentTree p2 = query(right, mid+1, b, i, j);
    segmentTree res;
    res.marge(p1, p2);
    return res;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int N = read();
    FOR(i, N) arr[i] = read();
    build(1, 1, N);
    int Q = read();
    while(Q--)
    {
        int type = read();
        if (type == 0)
        {
            int pos = read();
            int val = read();
            update(1, 1, N, pos, val);
        }
        else
        {
            int x = read();
            int y = read();
            if (x > y) swap(x, y);
            printf("%d\n", query(1, 1, N, x, y).getValue());
        }
    }
}