Segment Tree Course : CodeNCode Youtube (30 July 2020 : Merge Sort Tree practice problem added)

Thanks for such nice tutorial of lazy propogation. But i was solving multiple of 3 problem.
I did not understand why i am getting WA if i am performing lazy updates only if [ss,se] completely inside in [qs,qe].

But i am getting AC, if i am performing lazy updates for all nodes first. Later verify [ss,se] completely lies inside [qs,qe] or not.

Please look the below code and comments. Help me understand why it is happening?

void update(int si , int ss , int se , int qs , int qe)
{
if(ss > qe || se < qs) return;

if(lazy[si] != 0)   // moving this if condition to top its giving me AC. 
{
	int add = lazy[si];
	lazy[si] = 0;
	if(ss != se)
	{
		lazy[2*si] += add;
		lazy[2*si+1] += add;
	}
	add %= 3;
	for(int i=0;i<add;i++)
	{
		shift(si);
	}
}


if(ss >= qs && se <= qe)
{
	shift(si);
	if(ss != se)
	{
		lazy[2*si]++;
		lazy[2*si+1]++;
	}
	return;
}

int mid = (ss + se) / 2;
update(2*si , ss , mid , qs , qe);
update(2*si+1 , mid+1 , se , qs , qe);

st[si].ar[0] = st[2*si].ar[0] + st[2*si+1].ar[0];
st[si].ar[1] = st[2*si].ar[1] + st[2*si+1].ar[1];
st[si].ar[2] = st[2*si].ar[2] + st[2*si+1].ar[2];

}

I am trying to solve this problem using mergesort tree. But getting TLE. Could please help me out?
problem link : Coloring Tree | HackerRank
solution link:
XiHttO - Online C++0x Compiler & Debugging Tool - Ideone.com

Hello @waqar_ahmad224 Array Manipulation | HackerRank this question can be done with the help of segment trees right? If yes, then guide me a lil bit how to maintain maximum as there are many range queries and one more doubt is can we create an array of size 4*(10**7) ?
Waiting for your reply :slightly_smiling_face:

30 july 2020 : 1 practice problem added
E001 : K-Query | Spoj

Hi, Thanks for these amazing lectures.!
I was trying to solve the question “Multiple of 3” using lazy propagation…but I’m getting TLE using python(i know cpp is fast…).but have a look at my code and correct me if i am doing something wrong.
Code : https://ideone.com/w7pck3
i’ll try to code it in cpp…
Thanks again.!

Please add GSS1 from spoj

I think you should make a separate article asking help because I don’t code in python so it would be hard for me to tell you which part is consuming time.

I thought this was an easy problem , are you sure you want an editorial for this?

if anyone else wants this too please let me know , the more the merrier.

yes …i am unable to solve it

@waqar_ahmad224 Hi bhaiya, Please make a video on Heavy light decomposition

Please take a look on my solution
Help Ashu
I dont no where I am doing something wrong …

Hi codeNcode, I watched the number theory playlist videos, one of the hackerearth problems, I followed the video but I get WA in 3 testcases https://www.hackerearth.com/pt-br/submission/46336891/ what’s wrong?

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

const int MX=1e5;
const int INF=INT_MAX;

vector a(MX+1);
vector seg(4*MX+1);

struct SGT{
void build(int si ,int ss ,int se){
if(ss == se){
seg[si] = a[ss];
return;
}

	int mid = (ss + se) / 2;
	
	build(2*si ,ss ,mid);
	build(2*si+1 ,mid+1, se);
	
	seg[si] = min(seg[2*si] , seg[2*si+1]);
}

void build(vector<int> &a,int n){
	return build(1,1,n);
}

int query(int si, int ss, int se, int qs, int qe){
	//completely outside
	if(qs > se || qe < ss){
		return INF;
	}
	
	//completely inside
	if(ss >= qs && se <= qe){
		return seg[si];
	}
	
	int mid = (ss + se) / 2;
	
	int l = query(2*si, ss, mid, qs, qe);
	int r = query(2*si+1, mid+1, se, qs, qe);
	
	return min(l,r);
}

int query(int l,int r,int n){
	return query(1,1,n,l,r);
}

};

int main(){
SGT sgt;
int n;
cin>>n;

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

sgt.build(a,n);

int q;
cin>>q;

while(q--){
	int l,r;
	cin>>l>>r;
	
	cout<<sgt.query(l+1,r+1,n)<<"\n";
}

return 0;

}

i was trying to solve the RMQSQ problem from SPOJ using this solution but it is isn’t working and i am unable to find my mistake

for input
3
1 4 1
2
1 1
1 2

output is 4,1
but my output is 1,0

the only problem you are having is in input.
you are reading the input using 0-based index system (i is running from 0 to n-1 while reading input) and all other operations (query , build etc.) are using 1-based index system.

just read the input from 1 to n and everything else is absolutely correct

2 Likes

I am trying to solve Multiple of 3 question

I am using 0 based indexing here. But I am getting TLE .
Can anyone help me in figuring out the issue with it.

[MY Code]
(CodeChef: Practical coding for everyone)

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

int seg[400004][3] ; int lazy[400004];

void bulilSegtree(int index , int low , int high)
{
if (low == high)
{
seg[index][0] = 1;
seg[index][1] = 0;
seg[index][2] = 0;
return;
}

int mid = (low + high) / 2;
bulilSegtree(2 * index + 1, low , mid);
bulilSegtree(2 * index + 2, mid + 1, high);

seg[index][0] = (seg[2 * index + 1][0] + seg[2 * index + 2][0]);
seg[index][1] = (seg[2 * index + 1][1] + seg[2 * index + 2][1]);
seg[index][2] = (seg[2 * index + 1][2] + seg[2 * index + 2][2]);

}
void shift(int index)
{
int temp = seg[index][2];
seg[index][2] = seg[index][1];
seg[index][1] = seg[index][0];
seg[index][0] = temp;

}

int query(int index , int low , int high , int &l , int &r)
{

if (lazy[index] != 0)

{
int dx = lazy[index];
lazy[index] = 0;

if (low != high)
  lazy[2 * index + 1] += dx  , lazy[2 * index + 2] += dx; 

int totalCycle = dx%3;

for(int i=0;i<totalCycle;i++)
 shift(index);

}

if (l > high || r < low)
return 0;

if (low >= l && high <= r)
return seg[index][0];

int mid = (low + high) / 2;

int left = query(index * 2 + 1, low, mid, l, r);
int right = query(index * 2 + 2, mid + 1, high, l, r);

return (left + right);
}

void rangeUpdate(int index , int low , int high , int &l , int &r)
{
if (lazy[index] != 0)
{
int dx = lazy[index];
lazy[index] = 0;

if (low != high)
  lazy[2 * index + 1] += dx  , lazy[2 * index + 2] += dx; 

int totalCycle = dx%3;

for(int i=0;i<totalCycle;i++)
 shift(index);

}

if (l > high || r < low)
return ;

if (low >= l && high <= r)
{
shift(index);

if (low != high)
  lazy[2 * index + 1] += 1 , lazy[2 * index + 2] += 1;
return;

}

int mid = (low + high) / 2;

rangeUpdate(2 * index + 1, low , mid , l , r);
rangeUpdate(2 * index + 2 , mid + 1 , high , l , r);

seg[index][0] = seg[2 * index + 1][0] + seg[2 * index + 2][0];
seg[index][1] = seg[2 * index + 1][1] + seg[2 * index + 2][1];
seg[index][2] = seg[2 * index + 1][2] + seg[2 * index + 2][2];
}

void solveTestCases()
{
int n;
cin>>n;

int q;
cin>>q;

bulilSegtree(0 , 0 , n-1);

while (q--)
{
  int type;
  cin>>type;
  int a , b;
    cin>>a>>b;

  if(type == 0)
  {
    
    rangeUpdate(0,0,n-1,a,b);

  }else if(type ==1 )
  {
    cout<<query(0,0,n-1,a,b)<<endl;
    
  }
  
}


return;

}

int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

    solveTestCases ();  

return 0;
}

brother can you please explain why my python solution is giving TLE in the question “multiples of 3” which you have covered in your youtube channel by applying the same approach you have taught, and with the same approach in C++ it’s giving AC.

CodeChef: Practical coding for everyone please some one help how to solve this using merge sort tree…

You are given an array A of N integers and Q queries. Queries are of two types:

  1. l r v -> decrement the values of A between index l and r (both inclusive)
    by v.
  2. v -> print the index of the leftmost element whose value is less than v. If
    no such element exists then print -1.
    Input :
    First line contains two integers -> value of N and Q;
    Second line contains N space separated integers -> A[0] A[1] ------ A[N - 1]
    Each of the next Q lines contain queries.
    Query is of type
  3. t l r v
  4. t v
    Here t is the type of query (1 or 2).
    Output
    Print answer for every query of type 2.
    Limits :
    1 <= N, Q <= 100,000
    -1000,000,000 <= A[i] <= 1,000,000,000
    -1000,000,000 <= v <= 1,000,000,000
    0 <= l <= r < N
    1 <= t <= 2

Can anyone help me in this question.

I got AC for K-Query in Spoj, where same code is giving TLE on Codeforces.

Submission link on Codeforces:
Codeforces

Code:
#include <bits/stdc++.h>
#include <ext/rope>

#define pb push_back
#define ll long long
#define endl “\n”
#define MX 30005

#define W(t) while(t–)
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define rep(i,a,b) for(ll i = a; i <= b; i++)

using namespace std;
using namespace __gnu_cxx;

int a[MX], n, q, k;
vector segTree[4*MX];

void build(int node, int b, int e)
{
if (b == e) {
segTree[node].pb(a[b]);
return;
}

int mid = (b + e) / 2;
int left = node << 1;
int right = (node << 1) + 1;

build(left, b, mid);
build(right, mid + 1, e);

int i = 0, j = 0;

while (i < segTree[left].size() && j < segTree[right].size()) {
	if (segTree[left][i] <= segTree[right][j])
		segTree[node].pb(segTree[left][i]), i++;
	else
		segTree[node].pb(segTree[right][j]), j++;
}
while (i < segTree[left].size())
	segTree[node].pb(segTree[left][i]), i++;
while (j < segTree[right].size())
	segTree[node].pb(segTree[right][j]), j++;

}
int Query(int node, int b, int e, int l, int r, int k)
{
if (b > r || e < l) return 0;

if (b >= l && e <= r) {
	int indx = upper_bound(all(segTree[node]), k) - segTree[node].begin();
	if (indx == segTree[node].size()) return 0;
	else return (segTree[node].size() - indx);
}
int mid = (b + e) / 2;
int left = node << 1;
int right = (node << 1) + 1;

int r1 = Query(left, b, mid, l, r, k);
int r2 = Query(right, mid + 1, e, l, r, k);

return r1 + r2;

}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

cin >> n;
rep(i, 1, n) cin >> a[i];
build(1, 1, n);

cin >> q;

W(q)
{
	int l, r, k; cin >> l >> r >> k;
	cout << Query(1, 1, n, l, r, k) << endl;
}
return 0;

}
Any kind of help would be obliged. Thank you. :slight_smile:

Hi @waqar_ahmad224,

Thank you very much for your sequence of videos related to segment trees. These are very well explained! I just understood lazy propagation for segment trees for the first time :). May I ask if you have the code in Python for the lazy propagation?

Thanks again for these great videos.