Hey @vijju123 , I am also stuck on the same question. I have implemented the same thing that you have described in previous answers still I am getting WA. Could you please help! Code:

#include<bits/stdc++.h>
using namespace std;
long long MAX = 4000001;
vector <long long> tree, lazy, arr;
map <pair<int, int>, long long> dp;
map <pair<int, int>, long long> ::iterator it;
class Node
{
public:
  long long presum , postsum, maxsum, totalsum, left, right;
  Node *cleft, *cright;
  Node()
  {
    presum = -15008;
    postsum = -15008;
    maxsum = -15008;
    totalsum = -15008;
    cleft = NULL;
    cright = NULL;
  }
  void merge()
  {
    presum = max(cleft -> presum, cleft -> totalsum + cright -> presum);
    postsum = max(cleft -> postsum + cright -> totalsum, cright -> postsum);
    totalsum = cleft -> totalsum + cright -> totalsum;
    maxsum = max(max(cleft -> maxsum, cright -> maxsum), cleft -> postsum + cright -> presum);
  }
};

void build(Node* node, long long start, long long end)
{
  if(start == end)
  {
    node -> totalsum = arr[start];
    node -> maxsum = arr[start];
    node -> postsum = arr[start];
    node -> presum = arr[start];
    node -> left = node -> right = start;
  }
  else
  {
    node -> cleft = new Node;
    node -> cright = new Node;
    node -> left = start;
    node -> right = end;
    long long mid = (start + end)/2;
    build(node -> cleft, start, mid);
    build(node -> cright, mid + 1, end);
    node -> merge();
  }
}



Node* queryRange(Node* node, long long start, long long end, long long l, long long r)
{
    Node* a1;
    a1 = new Node;
    if(start > end || start > r || end < l)
        { 
          return a1;   }      
    if(start >= l && end <= r)             
        return node;
    long long mid = start +(end - start) / 2;
    a1->cleft = (queryRange(node -> cleft, start, mid, l, r));         
    a1->cright = (queryRange(node -> cright , mid + 1, end, l, r)); 
    a1 -> merge();
    return a1;
}

int main()
{
    long long n, query;
    Node *root = new Node;
    Node *ans;

        scanf("%lld", &n);

        arr.resize(n, 0);
        for(int i = 0; i < n; i++)
        {
          scanf("%lld", &arr[i]);
        }
        build(root, 0, n - 1);
        cin >> query;
        int p, q;
        while(query--)
        {
          scanf("%d %d", &p, &q);
          if(dp.find(make_pair(p, q)) == dp.end())
          {
            dp[make_pair(p, q)] = queryRange(root, 0, n - 1, p - 1, q - 1) -> maxsum ;

          }
          printf("%lld", dp[make_pair(p, q)]);
        }
        arr.clear();

    return 0;
}

@vijju123 Cleared Bro. Thanks a lot for taking the time and clearing my doubt.Will you recommend me any other good problems on Segment Trees?

Ok, so you want the reasoning behind it?

Firstly, I assume that you know why MaxSum of Left Node+ MaxSum Of Right node is wrong.

Now, say our nodes have information about sub-arrays- L={-20,10,10} (index say, 0 to 2) and R={10,10,-20} (index say, 3 to 5). Now our parent node stores by combining results of L and R. So parent node stores result for {-20,10,10,10,10,-20}.

Ofc, the answer for query is 10+10+10+10=40. But look at values.

For L, Sum=0, Maxsum=20, PrefixSum=0, Suffixsum=20. For R,Sum=0,Maxsum=20,PrefixSum=20,SuffixSum=0;

Now when we combine segments L and R, we get collective segment {-20,10,10,10,10,-20}. Focus on how this segment {10,10,10,10} got formed. Isnt it the "Best Suffix sum of node L + Best Prefix Sum of Node R"?

If you argue for Maxsum of L + Max sum of R, then an easy counter example is {10,10,-200,-200,10,10}. Maxsum of L + Maxsum of R gives 20+20=40, but its not possible because positions must be contiguous.

But when we add suffix and prefix sum, then its obvious that the positions are contiguous, for we calculated those 2 that way!

Still any doubt that why its Best Suffix Sum of L + Best Prefix Sum of R?

@vijju123 Please find my mistake, I wrote the getMaxSum function as you mentioned above

define ll long long
using namespace std;
struct node
{
    ll sum;
    ll maxPrefixSum;
    ll maxSuffixSum;
    ll maxSum;
};
node segarr[4*50010];
ll arr[50010];
void constructST(ll arr[],node segarr[],ll l,ll r,ll pos)
{
    if(l==r)
    {
        segarr[pos].sum=arr[l];
        segarr[pos].maxPrefixSum=arr[l];
        segarr[pos].maxSuffixSum=arr[l];
        segarr[pos].maxSum=arr[l];
    }
    else
    {
        ll mid=(l+r)/2;
        constructST(arr,segarr,l,mid,2pos+1);
        constructST(arr,segarr,mid+1,r,2pos+2);
        segarr[pos].sum=segarr[2pos+1].sum+segarr[2pos+2].sum;
        segarr[pos].maxPrefixSum=max(segarr[2pos+1].maxPrefixSum,
                                        segarr[2pos+1].sum+segarr[2pos+2].maxPrefixSum);
        segarr[pos].maxSuffixSum=max(segarr[2pos+2].maxSuffixSum,
                                        segarr[2pos+2].sum+segarr[2pos+1].maxSuffixSum);
        segarr[pos].maxSum=max(segarr[2pos+1].maxSuffixSum+segarr[2pos+2].maxPrefixSum,
                                        max(segarr[2pos+1].maxSum,segarr[2pos+2].maxSum));
    }
}
ll getMaxSum(node segarr[],ll l,ll r,ll qs,ll qe,ll pos)
{
    if(qs>r || qe< l)
        return -16000;
    if(qs<=l && qe >= r)
    return segarr[pos].maxSum;
    ll mid=(l+r)/2;
    ll a=getMaxSum(segarr,l,mid,qs,qe,2pos+1);
    ll b=getMaxSum(segarr,mid+1,r,qs,qe,2pos+2);
    return max(max(a,b),a+b); 

}
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=0;i< n;i++)
    scanf("%lld",&arr[i]);
    constructST(arr,segarr,0,n-1,0);
    ll m;
    scanf("%lld",&m);
    while(m--)
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        ll ans=getMaxSum(segarr,0,n-1,a,b,0);
        printf("%lld\n",ans);
    }
    return 0;
}