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

tutorial
, ,
1

Hello Codechef Community this CodeNCode

I am working on segment tree course project in which I will be covering concepts as easy as range minimum query to persistence segment tree.

The course is built emphasizing on “learning by doing” methodology , so we will be solving problems after learning concepts to implement those concepts to make sure we have understood those concepts and to know if we are having some problems with that or we are good to go.

I am not a professional trainer so you can expect I will not be “Perfect” In teaching but I will try to give my best shot.

The best thing about the course is I will be available to take on your queries and try to help you out here in the comments section.If you have any doubt or query make sure you ask here not on youtube (There are many reasons for it).

Here is the list of lectures added in the course till now.
L00 : Course Overview
L01 : Introduction to Segment Tree
L02 : Segment Tree Implementation
L03 : RMQSQ (SPOJ) | Practice Problem
L04 : Segment Tree Point Updates
E001 : Help Ashu (HackerEarth) | Point Update Practice Problem
L05 : Lazy Propagation Introduction
L06 : Lazy Propagation Implementation
E001 : Multiples of 3 (Medium) | Codechef
L07 : Introduction To Merge Sort Tree
L08 : Merge Sort Tree Implementation & Space Complexity
L09 : Merge Sort Tree Answering queries
E001 : K-Query | Spoj


There are more lectures to be added. If you have any doubts/query/suggestion , please let me know in the comments. Thank you for your valuable time. CodeNCode out.
37 Likes
2

8 May 2020 : 1 new Video added
E001 : Help Ashu (HackerEarth) | Point Update Practice Problem

4 Likes
3

This was asked by some person on youtube i think this method is fine:
can we do this question by making all odd elements as 1 and even elements as 0 and then build a prefix sum array of this. but for update we will have to use lazy propagation instead. in build also we will have to consider sum only?? please reply

4

I think what he wanted to say is that instead of having a segment tree with pairs you can make a segment tree with int array and store only odd or even numbers in a range.

so , make a segment tree to store only odd numbers in a range , when a query comes to count odd numbers in a range you can run a query on this segment tree , if query comes for even number answer would be : total numbers in range - odd numbers in that range.

Yes this will work , no need of lazy propagation simple point update will work.

3 Likes
5

17 May 2020 : 1 new video added
L05 : Lazy Propagation Introduction

2 Likes
6

Bro when will you make videos on centroid decomposition :shushing_face: I tried to learn from a blog but i am not getting it completely

1 Like
7

soon , I think that is part of my query on trees series.

2 Likes
8

21 May 2020 : 1 new lecture added
L06 : Lazy Propagation Implementation

3 Likes
9

YES. YOU’R RIGHT.

#include<bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false);cin.tie(NULL);
#define fr(i,a,b) for(long long i=a;i<b;i++)
#define mp make_pair
#define endl “\n”
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef vector vl;
const int mod=1e9+7;
const int inf = 1e9;
#define debug(x) cout << #x << " is " << x << endl
#define all(x) x.begin(), x.end()
const int N = 1e5+5;
int arr[N];
int seg[4*N];

void build_tree(int si, int ss, int se){
if(ss == se){
if(arr[ss]%2)
seg[si] = 1;
else
seg[si] = 0;
return;
}
int mid = ss + (se-ss)/2;
build_tree(2si, ss, mid);
build_tree(2si+1, mid+1, se);

seg[si] = seg[2si] + seg[2si+1];
}

void update(int si, int ss, int se, int qi){
if(ss == se){
if(arr[qi]%2)
seg[si] = 1;
else
seg[si] = 0;
return;
}
int mid = ss + (se-ss)/2;
if(qi <= mid)
update(2si, ss, mid, qi);
else
update(2si+1, mid+1, se, qi);

seg[si] = seg[2si] + seg[2si+1];
}

int getAns(int si, int ss, int se, int qs, int qe){
if(qs>se || qe<ss)
return 0;
if(ss>=qs && se<=qe)
return seg[si];
int mid = ss + (se-ss)/2;

return getAns(2si, ss, mid, qs, qe) + getAns(2si+1, mid+1, se, qs, qe);
}

int main(){

int n;
cin >> n;
for(int i=1; i<=n; i++)
  cin >> arr[i];
build_tree(1, 1, n);
//for(int i=1; i<=12; i++)
  //cout << i << " " << seg[i] << endl;
//cout << endl;
int q;
cin >> q;
while(q--){
  int a, l, r;
  cin >> a >> l >> r;
  if(a == 0){
    if(arr[l]%2 == r%2) continue;
    arr[l] = r;
    update(1, 1, n, l);
  }
  else{
    int odd = getAns(1, 1, n, l ,r);
    if(a == 2)
      cout << odd << endl;
    else
      cout << ((r-l+1) - odd) << endl;
  }
}

return 0;

}

10

16 June 2020 : Added new lecture
E001 : Multiples of 3 (Medium) | Codechef

1 Like
11

18 June 2020 : Merge Sort Tree lecture added
L07 : Introduction To Merge Sort Tree

3 Likes
12

Please complete the whole series…

13

yes , that’s what I am doing

2 Likes
14

22 June 2020 : new lecture added

L08 : Merge Sort Tree Implementation & Space Complexity

2 Likes
15

26 june 2020 : new lecture added
L09 : Merge Sort Tree Answering queries

1 Like
16

Sir upload one more problem on merge sort trees from hackerrank ,… Piz…

17

sure , if you have any problem suggestion you can tell me

1 Like
18

Please add GSS1 explanation… Thanks

19

This (5 to 11 July) week’s lecture have been decided.
next week for sure.

2 Likes
20

plz upload solution of dragon den