silent_sky's blog

Segment trees c++
By silent_sky, history, 6 years ago, In English

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

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I understood them pretty well from here https://cp-algorithms.com/data_structures/segment_tree.html

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Searching for the first element greater than a given amount

    This task can be solved using binary search over max prefix queries with the Segment Tree. However, this will lead to a O(log2n) solution.

    Can you help me out with this, I am unable to understand what it means.

    Sorry I bumped an old post (Didn't see the time).

    → Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

become specialist and then learn segment trees ;)

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think you won't use segment tree now.there are many topics more important than it for your level.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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_R2sWyUtXSKiKlyvAw

I 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.

→ Reply