I've just learnt range minimum and maximum queries using segment trees.But when I implemented it on my own I'm getting wrong answer.Logically I don't find any mistake in my code but if any one can point it out then I would be really thankful.
Code in C++:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define gc getchar_unlocked
#define pc putchar_unlocked
#define LD long double
#define MAXN 19999999
#define max(a,b) ((a)>(b)?(a):(b))
LL P[MAXN+15];
LL ST[2*MAXN+25];
long N,M,i,A,B,K;
void build(long id,long L,long R)
{
long M=(L+R)>>1L;
long LCT=id<<1L;
long RCT=LCT+1L;
if(L==R)
{
ST[id]=P[L];
return;
}
build(LCT,L,M);
build(RCT,M+1,R);
}
//Range Update of segment tree
void updateST(long id,long L,long R,long Q1,long Q2,long val)
{
long M=(L+R)>>1L;
long LCT=id<<1L;
long RCT=LCT+1L;
if(L>Q2||R<Q1)
{
return;
}
if(L==Q1&&R==Q2)
{
ST[id]+=val;
return;
}
if(Q2<=M)
{
updateST(LCT,L,M,Q1,Q2,val);
}
else if(Q1>M)
{
updateST(RCT,M+1,R,Q1,Q2,val);
}
else
{
updateST(LCT,L,M,Q1,M,val);
updateST(RCT,M+1,R,M+1,Q2,val);
}
}
//Query for finding maximum element in a given range[Q1,Q2] and 1<=Q1,Q2<=N
LL query2(long id,long L,long R,long Q1,long Q2)
{
long M=(L+R)>>1;
long LCT=id<<1;
long RCT=LCT+1;
if(L>Q2||R<Q1)
{
return 0;
}
if(L==Q1&&R==Q2)
{
return ST[id];
}
if(Q2<=M)
{
return query2(LCT,L,M,Q1,Q2);
}
else if(Q1>M)
{
return query2(RCT,M+1,R,Q1,Q2);
}
else
{
LL G=query2(LCT,L,M,Q1,M);
LL H=query2(RCT,M+1,R,M+1,Q2);
LL RES=max(G,H);
return RES;
}
}
int main()
{
scanf("%ld %ld",&N,&M);
build(1,1,N);
for(i=0;i<M;i++)
{
scanf("%ld %ld %ld",&A,&B,&K);
updateST(1,1,N,A,B,K);
}
//Finding maximum element in range[1,N]]
cout<<query2(1,1,N,1,N);
return 0;
}
