SPOJ - GSS1 - Can you answer these queries I

/**
@author - Rumman BUET CSE'15
Problem - GSS1 - Can you answer these queries I (SPOJ)

Concept -
    # Segment Tree

    # So called - "Beginner Level" problem. -_-

    # I am a beginner level programmer. Every problem can be tough to me. This problem was tough.
    # Took me 3-4 days to understand the logic behind the solve.
    # From CF blog , tutorials.

Bangla -

     a.sum + b.prefix যদি ম্যাক্স হয় , তাহলে এই নোডের প্রিফিক্সে জমা থাকবে ,
            পরের নোডে গিয়ে সেটা রেজাল্টে কাউন্ট হবে - এভাবে চিন্তা করসিলাম ।
            আসলে এরকম প্রব্লেম এটাই ফার্স্ট । সি এফ এর ব্লগ পড়ে ৩-৪ দিন বুঝি নাই । পরে বুঝে করসি ।

            ১। প্রিফিক্সে থাকবে একটা নোডের আন্ডারে থাকা প্রথম ইন্ডেক্স থেকে শুরু হওয়া
            রেঞ্জের সরবোচ্চ consecutive sum. সেটা হতে পারে total sum এর সমান অথবা ছোট ।

            ২। সাফিক্সে ...... শেষ ইন্ডেক্স দিয়ে শেষ হওয়া রেঞ্জের ...... (১ এর মতোই ) ,

            ৩। sum মানে চাইল্ডের টোটাল সাম ।

            ৪। result এর মধ্যে বেস্ট টা রাখবো । যেহেতু consecutive sum , তাই ৩ টা হতে পারে ,

            প্রথমত , কোন ইন্টারভালের প্রথম ইন্ডেক্স থেকে শুরু হতে পারে ,
            দ্বিতীয়ত , কোণ ইন্টারভালের শেষ ইন্ডেক্স থেকে শুরু হতে পারে ।
            তৃতীয়ত , মাঝের কোথাও অর্থাৎ , দুই নোডের মাঝে বিস্তৃত থাকতে পারে ।
            এজন্য লেফট চাইল্ডের শেষ ইন্ডেক্স এর জন্য সরবোচ্চ যোগফল (suffix) আর
            রাইট চাইল্ডের প্রথম ইন্ডেক্স এর জন্য সরবোচ্চ যোগফল (prefix) -
            এ দুইটা যেহেতু একে অপরের সাথে কানেক্টেড , এজন্য এদের যোগ করে দিসি ।

    প্রশ্নঃ একে অপরের সাথে কানেক্টেড মানে ? উঃ লেফট নোডের শেষটা আর রাইট নোডের ফার্স্টের টা পরপর ২ টা সংখ্যা না ? হ্যাঁ । এটাই বুঝাইসি ।

    প্রশ্নঃ t.prefix = max( a.prefix, (a.sum + b.prefix) ) ; - এই লাইনের মানে কি ???
    উঃ যেহেতু consecutive sum , সেহেতু  , হতে পারে a এর প্রিফিক্স ই এন্সার , হতে পারে , a এর সাম এর সাথে b এর প্রিফিক্স যোগ হয়ে সেটাই ম্যাক্স  ।
    সাম যোগ করবো কারণ নাইলে consecutive হবে না ।

    ***** ওহ ভালো কথা । sum কিন্তু আসলে consecutive sum.

    ***** মোটামুটি এটুক বুঝলেই এনাফ । আর যদি না বুঝো , লাইগা থাকো । বুঝবা । আমার ৩ - ৪ দিন লাগসে । ছুইড়া ফেলতে ইচ্ছা করসে ।
    না । কঠিন এজন্য না । সহজ কিন্তু আমি পারতেসি না এজন্য ।

    *** কন্সেপ্ট যদি আরো ক্লিয়ার করতে পারি , আপডেট করে দিবো সমস্যা নাই । :3

    -   22 এপ্রিল , ২০১৭।
*/


#include <iostream>
#include<algorithm>
#include <cstdio>
#define ll                                      long long
#define fi                                      freopen("in.txt", "r", stdin)
#define fo                                      freopen("out.txt", "w", stdout)
#define m0(a) memset(a , 0 , sizeof(a))
#define m1(a) memset(a , -1 , sizeof(a))

#define mx 50003
using namespace std;

int i, j  ;

class node
{
public:
    int prefix ;
    int suffix ;
    int sum ;
    int result ;

    node(int tem)
    {
        prefix = suffix = sum = result = tem ;
    }

    node()
    {
        prefix = suffix = sum = result = -1000000 ;
    }
};


node combineChild(node a, node b)
{
    node t ;

    t.sum = a.sum + b.sum ;
    t.prefix = max( a.prefix, (a.sum + b.prefix) ) ;
    t.suffix = max( b.suffix, (b.sum + a.suffix) ) ;
    t.result = max( a.suffix + b.prefix, max(a.result, b.result)) ;

    /**************/
    t.result = max(t.result, t.prefix);
    t.result = max(t.result, t.suffix);
    t.result = max(t.result, t.sum);
    /**************/
    /// এই তিন টা লাইন অ্যাড করলেও হয় না করলেও হয় । বাট সেফ সাইডে থাকা আর কি । :3 জানি না কাজে লাগে কি না । তাহসীন ভাই এর কাছ থেকে ।
    return t ;
}


int A[mx] ;
node seg[mx*4] ;


node buildTree(int lo, int hi, int sp)
{
    if(lo == hi)
    {
        node n ;
        n = node(A[lo]) ;
        seg[sp] = n ;
        return seg[sp] ;
    }

    int mid ;
    mid = (lo+hi) / 2 ;

    node left = buildTree(lo, mid, 2*sp+1) ;
    node right = buildTree(mid + 1, hi, 2*sp + 2) ;

    seg[sp] = combineChild(left, right) ;

    return seg[sp] ;
}


node query(int lo, int hi, int sp)
{
    if(hi < i || lo > j)
    {
        node n;
        return n ;
    }
    if(lo >= i && hi <= j)
    {
        return seg[sp] ;
    }

    int mid ;
    mid = ( lo + hi ) / 2 ;

    node l, r ;

    l = query(lo, mid, 2*sp+1) ;
    r = query(mid + 1, hi, 2*sp + 2 ) ;

    return combineChild(l, r) ;
}

int main()
{
    for(int ii = 0 ; ii < mx ; ii++)
    {
        A[ii] = -1000000 ;
    }

    int N ;
    scanf("%d",&N) ;
    for(int ii = 0 ; ii < N ; ii++)
    {
        scanf("%d",&A[ii]) ;
    }

    buildTree(0, N-1, 0) ;

    int M ;
    scanf("%d",&M) ;

    while(M--)
    {
        scanf("%d %d", &i, &j) ;
        i-- ;
        j-- ;
        int ans ;

        ans = query(0, N-1, 0).result ;
        printf("%d\n",ans);
    }
    return 0 ;
}