Это видео недоступно.
Сожалеем об этом.
Masterclass: Range Query DS | Segment Trees | Fenwick Trees | Masterclasses By Striver
HTML-код
- Опубликовано: 26 ноя 2021
- In this lecture, Raj (Striver) conducts a Masterclass for Range Query DS. Watch the full video to know more about Segment Trees & Fenwick Trees for the benefit of all the coding and programming aspirants. Let's Crack It!
Relevel by Unacademy | Sign up now: relvl.co/se8h
Introducing Relevel, India’s first Test hiring platform by Unacademy which is helping jobseekers find their dream jobs.
Raj (Striver): CodeBeyond Learner Feedback Form - forms.gle/XLnL...
👉🏼 Playlist: • Special Session | Code...
Do Subscribe and be a part of the community for more such lessons here:
👉🏼 Subscribe to our channel: bit.ly/3vFurOU
👉🏼 Telegram: bit.ly/2WwFUop
Use Special Code “STRIVER” to get a Free Sample Relevel Test Paper 😍
👉🏻 Register today: relvl.co/se8h
Educator profile: unacademy.com/...
👉🏼 Subscribe today: unacademy.com/....
👉🏼 Goal Upcoming Class page: unacademy.com/....
------------------------------------------
Welcome to CodeBeyond - a new offering from Unacademy!
Learn to code from the World's Top Experts/Coders and get your dream job.
Our aim is to become a one-stop solution and bring to you a plethora of coding-related courses, hacks, information, and trends for all of you to reach your career goals.
We have some of the best educators at Unacademy to help you build the knowledge and skills in your chosen field, right from a beginner to a pro-level!
Subscribe to know more!
Download the Unacademy Learning App here:
👉🏼 Android: goo.gl/02OhYI
👉🏼 iOS: goo.gl/efbytP
Unacademy Subscription Benefits:
1. Learn from your favorite Educator
2. Dedicated DOUBT sessions
3. One Subscription, Unlimited Access
4. Real-time interaction with Educators
5. You can ask doubts in a live class
6. Limited students
7. Download the videos & watch them offline
#Range_Query #Segment_Trees #Fenwick_Trees #Programming
My first Seg tree class, gotta say this data structure is beautiful ❤️
In 1 hour, he teaches all the core concepts of segment trees with superb explanation. Loved it!
This knowledge is free, 3 hours of watching and you gain great information about a major data structure. Few people can have patience or eagerness to learn, because they know it will help them in the future.
2:16:00 Segment Tree+ Nodes 🔥🔥🔥
segment tree is clear now!!! thanks striver bhaiya and codebeyond!
If someone getting TLE while submitting the Sereja and Brackets problem then pass the string in the build function by reference.
thanks bro for helping i was amazed how i got tle
Thank u bhai I was stuck on this question for hours because of this problem only.
Thanks bro...
thanks bro
thanks bro
Bhaiya your teaching skill is superb.
Thanks a lot🙂.
You explained it so well. And apart from that you also taught us how to write a better code using Class and Objects. After your recursion playlist every DS seems very easy. Thank you for this tutorial. 🙏🙏
1:27:56 If you need two Segment trees, then without the OOP concept of creating a class as well I'm not able to understand why you'll need two copies of build, update, query functions. You can create two(or more) segment trees and just use these same functions for all of them.
I TOTALLY Agree BTW that using a Class makes things more simplified.
We can use the same code only if we pass both the arrays and a kind of book variable to know which tree we need to work!
Bohot sahi bhaiya ho aap,ekdam OP explanation
Thank you Striver bhai. Great Explanation 🙇🏻🙇🏻🙇🏻
All good but mid calculated by using (low + high) /2 can suffer from overflow. Should use :
mid = low + (high - low) / 2
How it will overflow sir please tell?
@@mohdhammadsiddiqui7598 Suppose all are int type variables and low and high are on the very close to INT_MAX then it is possible that their sum is greater than INT_MAX but low+(high-low)/2 will never let it overflow
@@AshishGupta-bi4rh understood thanx
thanks for such a wonderful lecture sir, you made this topic so much easy :)
Спасибо за ролик, но иногда я не понимал, что ты говоришь, когда переходил с английского на какой-то другой неизвестный мне язык :)
Очень информативно, с меня лайк!
1:55:00
D. Xenia and Bit Operations code
#include
using namespace std;
void buildSeg(int ind, int low, int high, int arr[], int seg[], bool isOr) {
// if overlapped completey
if(low == high) {
seg[ind] = arr[low];
return;
}
int mid = (low+high)/2;
// if no overlap
buildSeg(2*ind+1, low, mid, arr, seg, !isOr);
buildSeg(2*ind+2, mid+1, high, arr, seg, !isOr);
if(isOr) seg[ind] = seg[2*ind+1] | seg[2*ind+2];
else seg[ind] = seg[2*ind+1] ^ seg[2*ind+2];
}
void update(int ind, int low, int high, int seg[], int i, int val, bool isOr) {
if((low == high)){
seg[ind] = val;
return;
}
int mid = (low+high)/2;
if(i >n>>q;
int el = 1arr[i];
int seg[4*el] = {0};
if(n%2 == 0) buildSeg(0, 0, el-1, arr, seg, 0);
else buildSeg(0, 0, el-1, arr, seg, 1);
while(q--) {
int i, val;
cin>>i>>val;
i--;
if(n%2 == 0) update(0, 0, el-1, seg, i, val, 0);
else update(0, 0, el-1, seg, i, val, 1);
couto = 0;
this->c = 0;
this->f = 0;
}
};
Node mergeNodes(Node l, Node r) {
Node curr = Node(0, 0, 0);
int mn = min(l.o, r.c);
curr.f = (mn + (l.f + r.f));
curr.o = l.o + r.o - mn;
curr.c = l.c + r.c - mn;
return curr;
}
void buildSeg(int ind, int lo, int hi, Node seg[], string& s) {
if(lo == hi) {
Node temp = Node(0, 0, 0);
if(s[lo] == '(') {
temp.o = 1;
}else temp.c = 1;
seg[ind] = temp;
return;
}
int mid = (lo+hi)/2;
buildSeg(2*ind+1, lo, mid, seg, s);
buildSeg(2*ind+2, mid+1, hi, seg, s);
Node l = seg[2*ind+1];
Node r = seg[2*ind+2];
seg[ind] = mergeNodes(l, r);
}
Node getFull(int ind, int lo, int hi, int l, int r, Node seg[]) {
// if no overlap
if(lo > r || hi < l) {Node temp; return temp;}
if(lo >= l and r >= hi) return seg[ind];
int mid = (lo+hi)/2;
Node left = getFull(2*ind+1, lo, mid, l, r, seg);
Node right = getFull(2*ind+2, mid+1, hi, l, r, seg);
return mergeNodes(left, right);
}
int main() {
string s;
cin>>s;
int m; cin>>m;
int n = s.length();
Node seg[4*n];
buildSeg(0, 0, n-1, seg, s);
while(m) {
int l, r;cin>>l>>r;
l--;r--;
Node ans = getFull(0, 0, n-1, l, r, seg);
cout
I wonder how is your second code working. Because you wrote if(lo >= l and r >= hi) return seg[ind]; But cpp doesn't have and operator right?
complete overlap should be l == low && r == high instead of low>=l && high
Counting Inversion is wrong bhai because [4,6,5,3,2,1] for 6 according to your code there 5 pairs but actually the correct answer is 4 because i < j && a[i] > a[j] this not satisfied
Thanks buddy from Germany
How to get the notes of this class?
The coding style was awesome Bhai 😍😂
has striver shared his cp template
46:00:00
Striver bhaiya you teach so well.
Where can we access all the notes written in this class?
1:28:12
min/max function will be replaced by xor /or
you make it super easy
I was wondering.
Why don't we declare the segment tree and the array separately inside the class. In this way we can avoid passing the complete segment tree for every build and update function call. Because your implementation seems a bit heavy.
It is copied by reference, so we just copy the pointers not the whole array. So, no issue with time
@@rimurusama5070 Even by reference it's lenthier to write such a code
it is accepted with this code
1:22:21 my time stamp. Ab contest dene k baad continue krunga. Bhttt jyada interesting padhaya hai ♥️🙇🏻🙇🏻🙇🏻
great session!
My code for Count Inversion was accepted on Spoj but is throwing runtime error on Coding ninjas. I do not understand why
Because you are declaring seg array of size of maximum integer in the given array. It could be long long. But you can't declare an array of that much size .So it is giving runtime error.
one doubt in first problem in Xenian and bit operations
When I tried to submit it using vector instead of array it was giving me TLE but when I tried to do the same with array it was accepted.
can you please tell why it happened?
Pass the vector by reference instead of copy.
i did by vector and it passed
@@adityajain8535 What about Sereja and Brackets ? I did it by vector but it threw Tle even though i passed it by reference. Can you share your solution please ?? It's bugging me a lot
@@shivanshsingh176
#include
using namespace std;
struct Node{
int open = 0;
int close = 0;
int full = 0;
Node(){
open=0;
close=0;
full=0;
}
};
class seg{
public:
vectortree;
seg(int n){
tree.resize(4*n+1);
}
void build(int low, int high, int idx, string &s){
if(low>high)return;
if(low==high){
if(s[low]=='('){
tree[idx].open=1;
}else{
tree[idx].close=1;
}
return;
}
int mid=(low+high)/2;
build(low, mid, 2*idx+1, s);
build(mid+1, high, 2*idx+2, s);
int f=min(tree[2*idx+1].open, tree[2*idx+2].close);
tree[idx].full= tree[2*idx+1].full+tree[2*idx+2].full+f;
tree[idx].open =tree[2*idx+1].open+tree[2*idx+2].open-f;
tree[idx].close=tree[2*idx+2].close+tree[2*idx+1].close-f;
}
Node query(int l, int r, int low, int high, int idx){
if(highr)return Node();
if(low>=l && high>s;
int n=s.size();
seg sg(n);
sg.build(0, n-1, 0, s);
int q;
cin>>q;
while(q--){
int l, r;
cin>>l>>r;
l--;r--;
int ans= sg.query(l, r, 0, n-1, 0).full;
cout
1:10:10
thanks @striver
How to access notes?
1:54:45 king moment
but this code will give us TLE
30:18 zindagi jhand ho gyi hai ye laptop ke chalte
v
gd
2:00:00
Still beautiful @striver 🐐
solve it off
💌💌💌💌💌💌💌💌
clickbait sa kardiya, fenwick dekhne aaya tha mila nahi
isn't segment tree enough?
Bruh, dude is too arrogant 😂
people like you dont deserve him
😅