Segment Tree Range Minimum Query

[@MrEmin1987]

3 years ago I got job offer from Amazon because of this video, thanks Tushar.

[@aviralagarwal5871]

In which order did you start doing things for competitive prgramming?

[@uneebagha4633]

Hi Emin

[@hawktomnia007]

Amazon now asks such hard question?

[@shanugarg8428]

Hey all, if anyone C++ coder here, then do checkout : kzbin.info/www/bejne/gaurmouXpMSkars

[@tusharchouhan9606]

good bro i know i helped many

[@AnkitSharma-dx5yy]

I don't really know why people do not recommend this guy's videos. This is such a gem of a channel

[@phychematogy9031]

bcz he explains complex topics and most the people keep sticking to the easier ones. But if anyone is learning complex things they already know him. TUSHAR OP🔥🔥🔥

[@roh9934]

You are one of the best Teachers in the world of CS.Can easily take down Highly rated Professors.

[@DenisG631]

The BEST! I tried to understand the segment tree explanation from wiki and code forces but I just didn't get it. You made it so easy to understand!!! Thank you!

[@nvjrane]

I used to think segment trees is some abstract concept. You have made it so easy. Thanks a ton!

[@TheGamerGuy201]

i love how you always explain the recursion as well with a well labeled table...makes things very easy.

[@amritjha2802]

Amazingly explained!! Clearly, the best introductory video available on segment trees as per me. Thank you Sir!

[@oshogarg5215]

best explaination of segment tree on KZbin, we need people like you.

[@killerthoughts6150]

the only man on the internet to nail this explanation

[@anyu8109]

You got a talent of teaching. I have watched your video for kmp and segment tree, and you explained so clearly and so easy to understand.

[@nguyenhunginh8560]

there is a language barrier between me and him , but with a little help from gg translate , it is easy to understand the algorithms .I love this guy.

[@jahirulislammonir3490]

My heartiest thanks to you man,,, Your recursion explanation is one of the finest part of this video... Carry on :)

[@shashankrajholavanalli2868]

Awesome job. Very well done. Never seen a recursive function explanation so precise.

[@sammy-zo6sl]

I have improved my coding a lot from your videos. Keep up the great work

[@gauravjha6554]

Best Video on Segment Tree....I understood the concept so clearly just because of you...Thanks you so much Sir

[@pranavganorkar2379]

Best video in KZbin on Segment Tree...Understood it Perfectly...!!! Many thanks.....

[@anhadsingh4609]

+Pranav Ganorkar Very true.

[@EalhamAlMusabbir]

+Pranav Ganorkar Yes... best video in KZbin on Segment Tree.... :) And thanks a lot for ur effort , sir...

[@vishalsheth1888]

Best explanation! I will join the chorus to request a video on lazy propagation techniques.Lots of competitive programmers will appreciate it!

[@naughtyrishan]

Thanks a lot. Please keep uploading such videos. You help many. Your explanation along with the codes line by line really helps a lot in actual implementation. Thanks again.

[@S4EProductions]

Many thanks for this, great and easy to understand explanation, and everything was very well-made, including subtitles and everything else. Thank you for helping us, expecting nothing in return. Cheers

[@adityak1511]

Great explanation Tushar! You're helping a lot of people here... Keep up the good work!!

[@priyanksingh6818]

AMAZING!!! I was struggling how to implement trees on questions and you made it clear in single vedio.

[@abhaypatil2000]

tbh implementation for trees and segment trees are very different. Seg tree -> vector/array and tree -> class/ structure

[@bedapudisrinivas852]

This video made 6 years ago and this video came first when i search about segment tree. Content matters

[@ihatesaturn69420]

Kindest regards to you sir, I’ve been having much difficulty understanding this concept. Thank you so much!

[@vinayak_98]

this is beyond the doubt...one of the most beautiful explanation for a segment tree..thanks!

[@AlexandrBorschchev]

This guy is flawless in teaching!

[@huawu8706]

Thanks, Tushar, you always give us a very detailed explanation.

[@avinashchaurasiya6497]

Amazing video, clear to the point and the way you explain recursive calls is impressive. Thanks.

[@apam5432]

Hey there is an issue in the explanation, at 25:55, where u take value 4 from leaf, which should actually be 2. Other than that explanation was really great. Thanks for creating these videos

[@a7medoka]

You have no idea how happy i am after seeing this video someone explained this to me and i didn't understand a thing , but you really made it simple , thanks a lot . I guess I will be visiting your channel quite a lot :)

[@codeeasy855]

You have some really great videos Tushar. This is the best explanation from an implementation point of view. Thanks!

[@algorithmimplementer415]

You are amazing! The way you built the tree and explained - just amazing!

[@prateeksoni2294]

one easily see the effort behind this wonderful video. Thank You. Really helpful

[@varuntanmay21]

Awesome exposition of this interesting data structure. I think it could n't have been better. -> You explained motivation for this ds. -> Cost of creation in terms of time, space complexity. -> Detailed algo with illustrations. Your approach shows how well you understand this ds.

[@ashishdey9429]

Excellent. Brilliant way of explaining recursion. You are the man dude (Y)

[@iamdipankarj]

Thank you! I was struggling with segment tree till now.

[@dmitrykoval5613]

great explanation, thanks a lot. the only thing I'd like to point out is the way the middle element is calculated. Instead, I would count it like this (high - low) / 2 + low

[@harrygray6770]

I was told to watch the video again if i didnt get the 4n requirement so i watched again and got it. 🙂

[@SatyanarayanaBolenedi]

Good one!! I like the way you explained, how to construction segmentTree with the help of tabulation. Tushar.. you are Awesome!!

[@alok696969]

Thanks a lot Tushar for creating these videos !!! Really helps in clearing out the concepts while preparing for interviews.

[@realstory5818]

thanks bro realy helped me to prepare for olympics

[@Nerraruzi]

Outstanding presentation, very clear and accessible!

[@Sushil2874]

I mean this is the best explanation that i can get of this..!! Thank you so much for such great explanation..!!

[@marwanalaa3962]

It is very helpful and it is great to explain a recursive function till the end. thanks a lot :)

[@ankishbansal420]

Thanks tushar, you are legend in ds/algo. I struggle with this entire day, but you made my day. Thanks

[@sridevip.v.4243]

Tushar thankyou😊😊😊you made the concept so easyyy

[@meganlee5897]

Several interesting points related to segment tree worth chewing 1) how to calculate a ceiling number of power of 2. 2) why exactly worst case is 4 times lgn 3) how to do updates of the tree corresponding to update/append/deletion in original array

[@briankarcher8338]

I know it's 4 years late, but any update to a segment tree requires a recreation of the tree since the aggregates get changed up the tree. (which is O(n) time).

[@uditkaushik]

Sir your lectures are just amazing ,the way in which you explain things makes me feel BETTER :P . Sir I have a request please upload a video on maximum sub array problem using segment tree. I'll be highly obliged to you !! Thanks sir :) !!

[@AkshayAradhya]

WOW Thank you so much.Your resources really help me better at programming competitions

[@namanrastogi4501]

nice work. keep doing such videos on competitive programming.

[@shobhitsrivastava4496]

You are great, man may god bless you. your deserve a lot more subscribers!!

[@rajeevkumaryadav4046]

that's the dought I had rest the videos you put on are too good and helpful.thank you

[@mojahidislam9717]

it was a great video..i was looking on d internet regarding segment tree but no one has explained it better than u particularly d way u explain your code....Sir,if u could put videos on other topics which r necessary for competitive coding as it is difficult to get those contents on internet.. please put videos on how to solve problems on greedy concepts and other algorithmic concepts if possible by taking some problems of spoj ...

[@anoohyabollampally9733]

Excellent , understood in the very first go. Thanks.

[@kaivanmehta5771]

Amazing explanation, please cover updating a segment tree. Thanks!

[@dhiaeddinegharsallah2923]

Thank you so much dude ! I was struggling to understand Segment Tree until I have found your video ! I ow you a lot man ! You're awesome (y) (y)

[@AmanSingh-wb9ev]

Nice video ..really helped me ..to write my first code in segment tree

[@shivammittal704]

Really recursion is damn powerful, very well explained sir!

[@KrishnaKumar-yn9wf]

But if used in production you get fired.

[@balasahebdabhade3091]

Thanks a lot sharing. Simple and best explaination of segment tree. It would be great if can share one video on Fenwick tree or binary indexed tree.

[@AshishRawat-zl6te]

awesome video..great way to explain recursion for creation....really helped a lot....thanx......

[@ankitomss]

I might be wrong, but your function for construction does not quite work for this input :( n = 1000 nums = [1259, 7119, 6806, 8924, 8114, 3797, 6788, 3735, 6695, 7189, 5028, 2092, 8103, 2206, 3708, 7873, 7572, 6687, 8652, 7282, 3277, 6846, 9332, 3435, 6719, 8943, 8622, 1840, 792, 372, 7334, 6099, 4784, 1117, 7044, 2315, 7991, 9596, 8895, 4576, 8722, 3612, 4586, 5883, 2433, 7285, 6223, 2580, 7573, 3117, 8165, 3342, 3357, 2769, 6344, 5067, 8755, 2049, 7195, 215, 5323, 7070, 8046, 2686, 2440, 8114, 1011, 3693, 5668, 5489, 6513, 9594, 9506, 1313, 1374, 3290, 7590, 5154, 2654, 4843, 7988, 3580, 7873, 6744, 6768, 3804, 5554, 3562, 2627, 4922, 1801, 9958, 5989, 6788, 3859, 6487, 5699, 4447, 9750, 9274, 2482, 7863, 9630, 8583, 98, 4567, 3306, 4633, 1010, 9373, 9404, 213, 1087, 7753, 172, 8286, 1648, 9423, 4179, 2283, 4208, 5196, 7697, 1195, 7448, 6118, 6454, 8352, 3741, 1759, 2582, 6717, 7911, 6371, 7448, 4392, 6023, 7352, 5916, 963, 5821, 5840, 2376, 7848, 3711, 7953, 8138, 6278, 8253, 1171, 3208, 257, 3919, 7908, 6496, 9360, 1350, 3414, 9776, 8611, 2276, 9385, 3363, 8577, 4775, 7425, 9991, 812, 5321, 5080, 7370, 8739, 9474, 590, 915, 4026, 8163, 5482, 2941, 4770, 668, 9511, 8508, 3446, 6225, 5190, 4645, 7699, 8662, 6298, 1630, 1712, 4531, 9834, 5709, 5779, 9190, 7009, 6062, 2740, 5774, 9232, 7426, 6612, 676, 8336, 8072, 9322, 5791, 6724, 2298, 1489, 6040, 8098, 7699, 7392, 2560, 9874, 2135, 3099, 8664, 2977, 3802, 2031, 5540, 5876, 5588, 8144, 3716, 807, 7419, 6162, 4142, 305, 4891, 9847, 2404, 1355, 5899, 8765, 5714, 9242, 7447, 8877, 6018, 6257, 7386, 9244, 6200, 3430, 169, 1092, 76, 7853, 9432, 857, 3749, 2157, 1855, 6460, 2095, 45, 8013, 4187, 3872, 7798, 5876, 6981, 8603, 5619, 2973, 2146, 2632, 8345, 1376, 3456, 1044, 8218, 1349, 8265, 2098, 7248, 1580, 1037, 4214, 9200, 7441, 8590, 1906, 2039, 4388, 8536, 8254, 1292, 9270, 3621, 1701, 4497, 8306, 1127, 124, 726, 1544, 6657, 592, 8538, 302, 3246, 4502, 6897, 7576, 588, 3587, 3701, 1738, 6669, 6512, 2331, 8789, 3201, 669, 6168, 5889, 8750, 1067, 855, 2523, 7797, 1033, 8826, 7541, 2061, 2018, 5171, 7543, 4440, 6230, 1662, 5998, 1591, 8138, 713, 8866, 875, 6067, 364, 7426, 2114, 2114, 9304, 4237, 4285, 231, 9956, 6560, 7881, 9237, 5266, 3950, 86, 9227, 8236, 3797, 383, 5332, 5829, 7454, 7343, 7600, 3647, 2964, 4578, 1588, 2048, 2016, 478, 5181, 6395, 456, 2044, 5332, 7555, 1767, 8044, 1660, 3193, 5163, 6671, 9026, 2564, 1223, 334, 6569, 8624, 3394, 6843, 1490, 6030, 7711, 6788, 5011, 154, 4756, 8032, 5560, 6964, 6830, 9751, 5443, 5422, 9710, 4719, 9663, 5842, 1880, 1000, 1407, 2880, 1445, 3741, 3087, 7266, 7721, 3796, 2467, 7770, 8895, 5643, 2551, 3279, 4898, 9565, 7565, 1545, 6061, 2950, 2317, 9740, 6795, 2547, 2253, 3642, 4438, 3261, 6779, 2474, 963, 2097, 1332, 1066, 5715, 4769, 2485, 6514, 1672, 7067, 4472, 1232, 6518, 1436, 3346, 3751, 2596, 4294, 1069, 2645, 6347, 3034, 1642, 7721, 3522, 7060, 3199, 7585, 1032, 4000, 5797, 3655, 280, 7340, 2560, 1670, 9408, 3317, 1180, 8950, 8633, 8073, 3765, 8099, 4210, 323, 7884, 2229, 9221, 4187, 6942, 9972, 865, 2494, 4541, 6242, 3362, 473, 5358, 5270, 3614, 5427, 326, 8861, 2292, 666, 856, 5123, 1925, 6554, 5767, 1914, 8016, 521, 1261, 2945, 8909, 5947, 6634, 6240, 8015, 9938, 7920, 4385, 5856, 342, 8709, 4143, 1094, 4075, 1122, 6170, 7664, 1683, 5348, 9296, 8110, 8012, 6500, 7792, 9360, 6232, 9389, 5636, 4833, 5498, 7416, 2124, 5144, 5179, 4884, 9588, 5307, 9575, 9774, 7987, 3457, 1129, 6545, 833, 7357, 3683, 3331, 8308, 6117, 5785, 7831, 654, 7341, 2965, 3773, 8598, 8698, 2991, 5459, 713, 958, 9404, 7191, 1463, 1595, 9986, 1505, 2963, 5107, 979, 9114, 4369, 8637, 4810, 3819, 1629, 7404, 6067, 6736, 2194, 6911, 7408, 1101, 6504, 627, 1231, 5123, 8715, 8608, 4883, 3647, 1893, 9220, 7823, 7318, 8547, 7590, 3207, 1127, 6236, 181, 3666, 620, 9235, 9695, 343, 328, 9551, 8599, 9004, 690, 9581, 2341, 1421, 3824, 7072, 2014, 3829, 6792, 1471, 6872, 6425, 5454, 6400, 6533, 8930, 7534, 8531, 5496, 1342, 9722, 9871, 7073, 4725, 9152, 3232, 7378, 7726, 4027, 8763, 8881, 510, 9643, 9397, 9428, 2924, 1097, 2536, 5317, 1618, 3013, 7892, 8463, 3286, 2859, 6066, 2881, 4637, 982, 1204, 4959, 9431, 4405, 4983, 7583, 3149, 8364, 4263, 2604, 702, 1293, 7984, 139, 1240, 479, 1139, 4314, 7372, 7215, 414, 2366, 4335, 2833, 4822, 5829, 8019, 2645, 2367, 1886, 9197, 2180, 2350, 1331, 8956, 7571, 2728, 9637, 1755, 5908, 417, 4088, 2942, 7850, 8170, 6357, 5618, 6783, 9229, 1142, 4596, 6170, 8177, 1878, 3330, 8419, 2965, 8715, 6167, 7948, 6678, 1989, 8960, 1345, 9280, 3836, 7962, 247, 682, 2057, 4575, 3794, 7559, 2922, 1001, 9275, 6134, 6592, 2136, 9974, 8497, 8309, 9769, 8709, 3605, 3256, 4524, 3424, 2499, 3191, 7222, 2012, 7981, 7759, 9447, 2980, 6743, 3383, 9264, 7503, 4175, 7464, 1417, 1570, 9851, 5342, 4450, 6466, 3542, 7114, 5641, 6886, 9963, 4509, 9167, 5826, 3727, 5897, 3645, 2480, 6604, 1087, 8424, 3165, 8047, 27, 8261, 5941, 3152, 425, 5662, 2908, 1925, 201, 6848, 580, 6115, 528, 7615, 1658, 2523, 1438, 1676, 7385, 5481, 8732, 5140, 9254, 7195, 5816, 5908, 9642, 4033, 3859, 2403, 5365, 2288, 5348, 4133, 160, 5091, 9932, 7250, 3841, 5474, 637, 9038, 7955, 8896, 4036, 2425, 8470, 6631, 4245, 8629, 4661, 5295, 8468, 7582, 655, 5940, 1172, 9507, 6541, 8985, 5687, 4641, 9870, 7119, 6128, 6507, 3305, 9887, 9084, 9776, 9985, 3110, 3156, 7004, 1543, 896, 1814, 1927, 6219, 5085, 7975, 4452, 772, 1605, 61, 8260, 5315, 5358, 2937, 8388, 3433, 6076, 871, 4724, 3923, 9950, 1650, 1301, 3741, 4843, 2542, 4312, 5413, 3687, 5322, 546, 5272, 4324, 3421, 2479, 3705, 4093, 2014, 6183, 3971, 7655, 1064, 2227, 2257, 2922, 7257, 9913, 1597, 315, 9501, 1356, 4164, 3671, 8297, 785, 4682, 4661, 7497, 5906, 944, 26, 8661, 2002, 5796, 7537, 8367, 1235, 5765, 5177, 5757, 1076, 1441, 8510, 1906, 4997, 9, 9195, 1344, 6154, 3717, 8844, 8219, 8079, 4959, 3438, 4426, 9100, 4710, 1779, 8288, 7674, 8213, 6778, 8695, 5209, 198, 7782, 7110, 7726, 4759, 3087, 315, 1807, 9833, 8525, 8128, 2478, 8444, 4091, 9576, 7624, 898, 8044, 1040, 3480, 6205, 7158, 4734, 2556]

[@ChristopherNemoNakamura]

Aaaah it makes so much sense now! Thank you for this great explanation!

[@yashagrawal6850]

at 25:11 you said it wrong when there is complete overlap and we return segTree[pos] where pos=4 and value is 2 so returning value should be 2 but you said it 4 !! Let me know if i m wrong.

[@shivamlakhwara5080]

I think you're right ....I also caught that in the first place he returned an index instead of a value.

[@mikenguyen91]

nice catch, I tried to add a comment but you already did.

[@derpfaceonigiri4950]

You're awesome sir, this helped me a lot in segment tree self studying :'D

[@karthikmucheli7930]

I just had this observation. The 2D matrix to find the min in an array is the segment tree if you consider top right corner as the root node.

[@ManishKumar-zt5sk]

best explanation so far...

[@vishalyadav-fy7mv]

Best explanation ever on segment tree

[@shikharsubedi4703]

thank you so much for such a thorough explanation. You got a new subscriber

[@Bala-go6cc]

Video was awesome...but somewhat fast..It's great...bro..thank you..

[@eavanshiarora887]

Cannot get a better explanation! Thankyou :)

[@siddharthagarwal8662]

Nice explanation of segment tree

[@GoodgameMaster]

You're making the best tutorials! Thanks a lot!!

[@parvezmulla3324]

The Best I have ever seen about Segment Tree!

[@deb232]

Sir, can you also explain 1. Suffix array 2. KMP 3. Flow problems 4. Maximum Bipartite matching You explain really well and they help me grasp the concepts. I ave been trying to wrap my head around these things for long!

[@sankarpati5549]

I scare to look into segment tree alg before watching this video . Thanks Tushar Roy

[@chinmayrakshit9872]

thanks sir your explanation is simple and auwsum.....helps me a lot for competitive programming... :)

[@arhankundu2516]

Thank you sir for this awesome explanation 😃

[@firefox-zzz]

Easy to understand ,simple code... Thank you very much ! :)

[@thexwines]

awesome way to explain recursion, thanks a lot sir

[@soumyajitdutta428]

Awesome way of explaining..Hats of and thanx

[@suniladitya1016]

your explanation is amazing

[@annafalvello8138]

Your videos are so helpful, thank you!

[@georgiossamaras5063]

Awesome and laconic introduction of Segment Trees, thanks!

[@hypernarutouzumaki]

Please post a video on Interval Tree ! Your videos helped me a lot !

[@laraibanwar1618]

Well my dear bro

[@shaileshpandey5697]

I really appreciate your contribution in increasing our knowledge. Can you please upload video on TRIE.

[@remusvalentin099]

Thank you man, you are great at explaining stuff, keep em comming!!

[@BipinOli90]

Thanks for making this. You rock Tushar. You da man :)

[@akshatb]

Wow I finally got it..Thanks man you are doing a really great job :)

[@vidhansharma1787]

best explanation of segment trees......

[@ujjawalgupta5303]

Thanks for this awesome explanation.

[@ShounakKundu]

Even before algoexpert and scalar existed, this guy was the ULTIMATE GOD of DSA. Too bad he did not continue his channel. It is a humongous loss for us all.

[@swetabjahazra8050]

Best explanation, cant be any better..........

[@SonuSonu-tk5pk]

A unique way of explaining recursion. Great video.

[@thinhvu6902]

Wow I love this tutorial, thank you so much!!!!

[@pulkitgupta8575]

tushar bhaiya ki jai ho jai ho ..... maza agaya

[@ChristianESL]

You are amazing. Thanks for the explanation 👍😊

[@depengluan7222]

Awesome explanation! Thanks, Tushar!

[@prasadchaudhari1001]

I think in the video, the segment tree should have been made on a array length which is not a power of two so that people can also understand how other elements that are not been used are also not effecting the segTree array

[@AbhimanyuKumar1992]

Hi Tushar, Can you make a video on persistent segment tree. Your video is really awesome. I couldn't find any better explanation than this .. Thanks

[@vikaskumarsherawat]

very informative video. Thanks Tushar. :)

[@JENISONGRACIOUS]

Very detailed. If possible put up a video on Update value too.

[@AishwaryaRadhakrishnan34]

Thank you so much for this brilliant explanation!