### meeooow's blog

By meeooow, history, 8 months ago, ,

Could someone please explain how to implement segment trees and how do they work ? I tried to go through many tutorials, but cannot wind my head around it.

Note : I am a Newbie

• -16

 » 8 months ago, # |   0 There are lots of tutorials out there with great graphics, code explaining the details, blah blah, so I'm not sure how much my comment can help. It is just a bit of intuition explanation.Take an array of items as the leaves of the tree, and build a tree so that at each higher level you merge the two nodes below on the lower level (I'm sure you've seen graphics).Now when you want to query a range, some of these nodes will cover a big range. Step down from the tree recursively and as long as the function you are querying over nodes is associative, you can just use all the highest-level nodes covering a range within the range you are querying. Why? It already contains all the data of the range it covers merged. So you won't need to re-compute and do all that work again. Now it is possible to prove that this is O(log n) time (assuming that the function is O(1) when applied to two items).Because you already computed the function over these ranges, whenever you walk down the tree again, you can save a lot of computation time. You will encounter O(log n) nodes/recursions max. There are proofs of this, but this is just the intuition.
 » 8 months ago, # |   +1 I understood them pretty well from here https://cp-algorithms.com/data_structures/segment_tree.html
 » 8 months ago, # |   +16 become specialist and then learn segment trees ;)
•  » » 8 months ago, # ^ | ← Rev. 2 →   -17 Good suggestion. And I will learn arrays after being master (if I ever reach). ;)
•  » » » 8 months ago, # ^ |   +22 He's not joking :|
•  » » » » 8 months ago, # ^ |   +13 Then I apologize
 » 8 months ago, # |   +9 I think you won't use segment tree now.there are many topics more important than it for your level.
 » 8 months ago, # |   0 This is my way to learning ST when I was newbie.At first, I find this channel on youtube : https://www.youtube.com/channel/UCZLJf_R2sWyUtXSKiKlyvAwI think his lecture is quite easy to understand how ST works basically. You can search for his segment tree video.When I was newbie, I just knew a bit how ST use and I couldn't code it :(After that, I try to solve some online problems on Codeforces or Spoj, ...On Spoj, I 'm Vietnamese so I can use vn.spoj.com and solve with tag ST, but you can also search "Spoj Segment tree" on Google, and find many good result like this " https://www.quora.com/What-are-some-SPOJ-CodeChef-problems-to-learn-segment-tree "On Codeforces, you can use filter problems for data structures and with your suitable difficulty. You should remember that not all of it can be solved by ST.You can also try ORDERSET-SPOJ, LIS-SPOJ, 380C-Codeforces, SPOJ-KQUERY and Lazy Propagation.With some first problems, don't be nervous if you need the solution. I often read their code and wrote it again. Now, I 'm not sure I can use ST well, but I can apply it for some non-too-hard problems and have my own ST coding style.I hope my learning ST way can help you.