kumaraditya1999

int get(int idx)
{
    int sum = 0;
    idx = idx + 1; // if your array is one based then remove this 
 
    while (idx>0) 
    {
        sum += BIT[idx]; // add the value
        idx -= idx & (-idx); // remove the last set bit
    } 

kumaraditya1999

void upd(int idx, int val) 
{  
    idx = idx + 1; // if your query is one based then remove this
    while (idx <= N){
       BIT[idx] += val;
       idx += idx & (-idx); 
    } 
}

kumaraditya1999

void build()
{
    for(int i=0; i<N; i++){
        upd(i, arr[i]); // call update function for all the indices
    }
}

kumaraditya1999

int range(int idx)
{
    return get(r) - get(l-1);
}

kumaraditya1999

int get(int x, int y) {
    int sum= 0;
    for (int i = x+1; i > 0; i -= i & (-i))
        for (int j = y+1; j > 0; j-= j & (-j))
            sum += BIT[i][j];
    return sum;
}

kumaraditya1999

void upd(int x, int y, int val) 
{  
    for (int i = x+1; i <= N; i += i & (-i))
        for (int j = y+1; j <= M; j+= j & (-j))
            BIT[i][j] += val;
}

kumaraditya1999

void updrange(int x,int y int val) 
{   
    // upd is the function that was described above
    upd(x, val);
    upd(y+1, -val);
}

int getPoint(int idx)
{
     //get is the function that was described above

kumaraditya1999

void upd(vector<int>&BIT, int idx, int val)
{
    idx = idx + 1; 
    while (idx <= N){
       BIT[idx] += val;
       idx += idx & (-idx); 
    }
}

void updrange(int l,int r,int val)

kumaraditya1999

// The structure of the node
// ps - max prefix sum, ss - max suffix sum, ts - total sum, ms - maximum subarray sum of the array
struct node{
   ll ps,ss,ts,ms;
};

node tree[4*N]; // tree to store the nodes
ll arr[N]; // the array given in the question

// helper function to create a node when

kumaraditya1999

// qs - querry start, qe - querry end, ss - segment start, se - segment end, si - segment index

node query(ll qs,ll qe,ll ss,ll se,ll si){
//  If there is no intersection between this segment and the query interval return an invalid node, it is just a dummy node
    if(qs>se || qe<ss || qs>qe || ss>se){
       return inv;
    }

//  if the segment lies completly inside then return this node
    if(ss>=qs && se<=qe){