# MAXBTY - Editorial

i tried that way,my query working fine but update is not,shall we discuss more on BIT for this problem?

I tried the logic of editorās solution and implemented it in Python. Can anybody tell me why am I getting TLE for my solution.

//Can anyone tell me what is wrong in this solution?
def make_list(A,N,L,R):
s=0
r=0
L.append(A[0])
R.append(A[N-1])
for i in range(1,N):
if L[i-1]>0:
L.append(A[i]+L[i-1])
else:
L.append(A[i])
if R[0]>0:
R.insert(0,A[N-1-i]+R[0])
else:
R.insert(0,A[N-1-i])

T=int(input())
for t in range(T):
L=[]
R=[]
N,Q=map(int,input().split())
A=[int(x) for x in input().split()]
make_list(A,N,L,R)
for q in range(Q):
v,x,y=input().split()
if v==āQā:
x,y=int(x),int(y)
s=0
for i in range(x,y-1):
s=s+A[i]
s=s+L[x-1]+R[y-1]
print(s)
elif v==āUā:
x,y=int(x),int(y)
A[x-1]=y
L=[]
R=[]
make_list(A,N,L,R)

@tmwilliamlin

there is very small and easy implementation
https://www.codechef.com/viewsolution/30709921
could somebody help me !!! i am getting wrong ans.

You are not updating the tree according to its lazy values when you perform querymin().

In Setterās Solution,
in queryMin function why is it that we have to return 0, if the STnodeās range is not inside the query interval of (i,j) ?
if we return 0 , then wouldnāt the returned zero affect the further actual querying ?

That is, if size of array is 5 and we call queryMin for (4,5) intervalā¦ the queryMin call for (1,3) returns 0 and if the minimum value returned by queryMin for (4,5) interval is +ve ; then the final answer will be given as 0 as the minimum value.
I checked that this code returns 0 instead of the actual positive value which was supposed to come.

So, shouldnāt the value returned for out of range condition be changed to infinity?
But thatās what i did(exactly same as that of setterās solution except for what i return) , getting some wrong answer for the sample test cases itself.

correct me if Iām wrong.

Is my basic logic is wrong?
if not i am getting wrong answer.

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

``````int t;
cin >> t;
while (t--)
{
int n, q, x, y;
cin >> n >> q;
char query;
int arr[n];
for (int i = 0; i < n; ++i)
cin >> arr[i];
while (q--)
{
cin >> query >> x >> y;
int xIndex = x - 1;
int yIndex = y - 1;
if (query == 'Q') {
int tmpsum = 0, lmax = 0, rmax = 0, sum = 0;

//left side max sum
for (int i = xIndex -1; i >= 0; i--)
{
if (lmax < tmpsum + arr[i])
{

lmax = tmpsum + arr[i];
}
tmpsum += arr[i];
}
tmpsum = 0;

//right side max sum
for (int i = yIndex + 1; i < n; i++)
{
if (rmax < tmpsum + arr[i])
{
rmax = tmpsum + arr[i];
}
tmpsum += arr[i];
}

//sum between x and y
for (int i = xIndex; i <= yIndex; ++i)
{
sum += arr[i];
}

//max sum
sum += rmax + lmax;
cout << sum << "\n";
} else {
arr[xIndex] = y;
}
}
}

return 0;
``````

}

Can you help me? Whats wrong with this?

What is negative prefix sum?

When each element of prefix sum array is multiplied by -1, we get the negative prefix sum array

Instead of maintaining 2 segment trees, i maintained values of segment sum (z), maximum prefix (y) and maximum suffix sum (x) at each node in the segment tree, then output max(z,x+z,y+z,x+y+z) . But I am getting a WA. Is my logic incorrect? Please help me find whatās wrong with my code: https://www.codechef.com/viewsolution/30749140

@tmwilliamlin

unofficial short editorial

1 Like

@jugshaurya william lin has explained the mysara solution on his youtube channel.

``````#include<bits/stdc++.h>
#define maxn 100001
#define maxt 500005
using namespace std;

struct node
{
long long x;
long long n;
};

struct node tree[maxt];

long long max(long long a,long long b)
{
if(a>b) return a;
else return b;
}

long long min(long long a,long long b)
{
if(a>b) return b;
else return a;
}

node build(long long pre[],int v,int l,int r)
{
if(l==r)
{
tree[v].x=pre[l];
tree[v].n=pre[l];
return tree[v];
}
else
{
node m1,m2;
int mid = (l+r)/2;
m1 = build(pre,2*v,l,mid);
m2 = build(pre,2*v+1,mid+1,r);
tree[v].x=max(m1.x,m2.x);
tree[v].n=min(m1.n,m2.n);
return tree[v];
}
}

long long Qx(int v,int l,int r,int x,int y)
{
if(l==x&&r==y)
{
return tree[v].x;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qx(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qx(2*v+1,mid+1,r,x,y);
}
return max(Qx(2*v,l,mid,x,mid),Qx(2*v+1,mid+1,r,mid+1,y));
}

long long Qn(int v,int l,int r,int x,int y)
{
if(l==x&&r==y)
{
return tree[v].n;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qn(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qn(2*v+1,mid+1,r,x,y);
}
return min(Qn(2*v,l,mid,x,mid),Qn(2*v+1,mid+1,r,mid+1,y));
}

node ux(int v,int l,int r,int x,long long add,long long pre[])
{
int mid=(l+r)/2;
if(l==r&&l>=x)
{
tree[v].x=pre[l];
tree[v].n=pre[l];
return tree[v];
}
if(x>=mid+1)
{
node m1=tree[2*v];
tree[v].x = max(m1.x,m2.x);
tree[v].n = max(m1.n,m2.n);
return tree[v];
}
node m1,m2;
tree[v].x = max(m1.x,m2.x);
tree[v].n = max(m1.n,m2.n);
return tree[v];
}

int main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n;
cin>>q;
long long b[n+1]={0};
long long pre[n+1]={0};
for(int i=1;i<=n;++i)
{
cin>>b[i];
pre[i]=b[i]+pre[i-1];
}
build(pre,1,1,n);
while(q--)
{
char w;
cin>>w;
if(w=='Q')
{
int x,y;
cin>>x>>y;
long long a,b;
a=Qx(1,1,n,y,n);
b=Qn(1,1,n,1,x-1);
if(b>0) b=0;
cout<<a-b<<endl;
}
else
{
int x;
long long y;
cin>>x;
cin>>y;
}
}
}
return 0;
}
``````

I have used segmented tree then also it is showing time limit exceeded. Please help, how can I optimize it further?

@jprm2 thanks bhai

Please tell me what is wrong in my code:

https://www.codechef.com/viewsolution/30761682

My Code is almost similar to setters code,thats why am asking