# WA in MAXBTR(segment tree- cookoff)

//segment tree(RMQ)

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

#define int long long int
#define ll int
const int maxn=100000;
int t[4*maxn],tt[4*maxn];
int lazyx[4*maxn],lazyy[4*maxn]; //for lazy propagation(range update)

void pushx(int v)
{
lazyx[2*v+1]+=lazyx[v];
lazyx[2*v+2]+=lazyx[v];
t[2*v+1]+=lazyx[v];
t[2*v+2]+=lazyx[v];
lazyx[v]=0;
}

void pushy(int v)
{
lazyy[2*v+1]+=lazyy[v];
lazyy[2*v+2]+=lazyy[v];
tt[2*v+1]+=lazyy[v];
tt[2*v+2]+=lazyy[v];
lazyy[v]=0;
}

int constructx(int* arr,  int st, int end, int si)
{
if(st==end)
{
t[si] = arr[st];
return t[si];
}

int mid = (st + end)/2;
constructx(arr,st, mid, 2*si + 1);
constructx(arr,mid+1, end, 2*si + 2);
t[si] = min(t[2*si+1],t[2*si+2]);
return t[si];
}

int queryx(int qs, int qe, int l, int r, int si)
{
if(qs<=l && qe>=r)
return t[si];

if(qs>r || qe<l)
return INT_MAX;          //change  acc. to question
else
{
pushx(si);
int mid = (l + r)/2;
int sum = min(queryx(qs, qe, l, mid, 2*si + 1), queryx(qs, qe, mid+1, r, 2*si + 2));
return sum;
}
}
void updatex( int x, int l, int r,int tl, int tr, int si)
{
if(l>r)
return;

if(l==tl && r==tr)
{
t[si] +=  x;
lazyx[si] += x;
}
else
{
pushx(si);
int mid = (l + r)/2;
updatex(x, tl, min(mid,tr),l,  mid , 2*si + 1);
updatex(x, max(mid+1,tl),tr, mid+1, r, 2*si + 2);
t[si] = min(t[2*si+1] , t[2*si+2]);
}
}
int constructy(int* arr,  int st, int end, int si)
{
if(st==end)
{
tt[si] = arr[st];
return tt[si];
}

int mid = (st + end)/2;
constructy(arr,st, mid, 2*si + 1);
constructy(arr,mid+1, end, 2*si + 2);
tt[si] = min(tt[2*si+1],tt[2*si+2]);
return tt[si];
}

int queryy(int qs, int qe, int l, int r, int si)
{
if(qs<=l && qe>=r)
return tt[si];

if(qs>r || qe<l)
return INT_MAX;          //change  acc. to question

pushy(si);
int mid = (l + r)/2;
int sum = min(queryy(qs, qe, l, mid, 2*si + 1), queryy(qs, qe, mid+1, r, 2*si + 2));
return sum;
}

void updatey( int x, int l, int r,int tl, int tr, int si)
{
if(l>r)
return;

if(l==tl && r==tr)
{
tt[si] +=  x;
lazyy[si] += x;
}
else
{
pushy(si);
int mid = (l + r)/2;
updatey(x, tl, min(mid,tr),l,  mid , 2*si + 1);
updatey(x, max(mid+1,tl),tr, mid+1, r, 2*si + 2);
tt[si] = min(tt[2*si+1] , tt[2*si+2]);
}
}

void solve()
{   int n,q;
cin>>n>>q;

int* arr = new int[n];

int sum=0;
for(int i=0; i<n; i++)
{
cin>>arr[i];
sum+=arr[i];
}

int prefix[n],sufix[n];
prefix[0]=arr[0];
sufix[n-1]=arr[n-1];

for (int i = 1; i < n; ++i)
{
prefix[i]=prefix[i-1]+arr[i];
sufix[n-i-1]=sufix[n-i]+arr[n-i-1];
}

for(int i=0; i<4*maxn; i++)
{ t[i] = 0;
lazyx[i]=0;
tt[i] = 0;
lazyy[i] = 0;
}

constructx(prefix, 0, n-1, 0);
constructy(sufix, 0, n-1, 0);

while(q--)
{
char ch;
cin>>ch;

if(ch=='Q')
{
int qs,qe;
cin>>qs>>qe;
qs--;
qe--;

int s1=0,s2=0;

if(qs!=0)
s1= queryx(0, qs-1, 0, n-1, 0);
if(qe!=n-1)
s2= queryy(qe+1,n-1, 0, n-1, 0);
//cout<<sum<<" "<<s1<<" "<<s2<<endl;

if(s1>0)
s1=0;
if(s2>0)
s2=0;
cout<<sum-s1-s2<<endl;
}

else
{
cin>>index;
index--;

arr[index]=temp;

}
}

}

int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

int t;
cin>>t;

while(t--)
solve();

}
``````