Почему я получаю TLE для этого кода для проблемы GSS1 на SPOJ? (С использованием дерева сегментов)

Question

Ссылка на проблему: - https://www.spoj.com/problems/GSS1

1. Я использую дерево сегментов.

   Информация об узле: -

2. maxSum -> максимальная сумма сегмента, представленного узлом.

3. Sum ---> Общая сумма сегмента. (Хотя я думаю, что в этом нет необходимости)
4. maxPrefixSum ---> максимально возможная сумма префикса в сегменте. т.е. начиная с первого элемента сегмента.
5. maxSuffixSum ---> то же самое, что и maxPrefixSum, но начиная с последнего элемента сегмента.

Расчет значений узла: -

( "res" - новый узел, "left" и "right" - его левый и правый потомки соответственно) res.Sum = left.Sum + right.Sum; res.maxSum = max (max (left.maxSum, right.maxSum), left.maxSuffixSum + right.maxPrefixSum); res.maxSuffixSum = max (left.maxSuffixSum + right.Sum, right.maxSuffixSum); res.maxPrefixSum = max (left.maxPrefixSum, left.Sum + right.maxPrefixSum);

КОД

#include<bits/stdc++.h>
using namespace std;

#define int long long int

class node
{
public:
    int Sum, maxSuffixSum, maxPrefixSum, maxSum;
    node()
    {
        Sum = maxSuffixSum = maxPrefixSum = maxSum = 0;
    }
};

node node_value(node left, node right)
{
    node res;
    res.Sum = left.Sum + right.Sum;
    res.maxSum = max(max(left.maxSum, right.maxSum), left.maxSuffixSum + right.maxPrefixSum);
    res.maxSuffixSum = max(left.maxSuffixSum + right.Sum, right.maxSuffixSum);
    res.maxPrefixSum = max(left.maxPrefixSum, left.Sum + right.maxPrefixSum);
    return res;
}

void makeSegmentTree(vector<int> arr, vector<node> &tree, int idx, int start, int finish)
{
    if(finish == start)
    {
        tree[idx].Sum = tree[idx].maxPrefixSum = tree[idx].maxSuffixSum = tree[idx].maxSum = arr[start];
        return;
    }

    int mid = start + (finish - start)/2;
    makeSegmentTree(arr, tree, 2*idx, start, mid);
    makeSegmentTree(arr, tree, 2*idx+1, mid+1, finish);
    tree[idx] = node_value(tree[2*idx], tree[2*idx + 1]);
}

node queryTree(vector<node> &tree, int idx, int start, int finish, int left, int right)
{
    if(start >= left && finish <= right)
    {
        return tree[idx];
    }
    else
    {
        int mid = start + (finish - start)/2;
        if(start <= left && right <= mid)
        {
            return queryTree(tree, 2*idx, start, mid, left, right);
        }
        else if(left > mid && right <= finish)
        {
            return queryTree(tree, 2*idx+1, mid+1, finish, left, right);
        }
        else
        {
            node ans1 = queryTree(tree, 2*idx, start, mid, left, mid);
            node ans2 = queryTree(tree, 2*idx+1, mid+1, finish, mid+1, right);
            return node_value(ans1, ans2);
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> arr(n+1, 0);
    for(int i=1;i<n+1;i++)
    {
        cin>>arr[i];
    }


    vector< node > tree(4*n);
    makeSegmentTree(arr, tree, 1, 1, n);

    int q;

    cin>>q;
    while(q--)
    {
        int x, y;
        cin>>x>>y;
        cout<<queryTree(tree, 1, 1, n, x, y).maxSum<<endl;
    }
    return 0;
}