Segment Tree Approach for problem solving

general
, , ,
1

I recently read about segment trees and their implementation but was unable to decide what values should I put on tree’s node to get the desired answer. Like I was solving SPOJ question GSS1, and finally did it with the help of articles available related to this question, where people store four values on a node to get an answer, but I didn’t understand how can I approach for solving these type of questions.

Maybe a little bit explanation of a question related to segment tree could help me to understand better.

EDIT: If someone can provide links to the problem related to segment trees in increasing order of difficulty, that would be a great help.

2 Likes
2

I am also in same lines. New to segment trees and concept of trees altogether. From what i perceived so far, deciding what to store in nodes is exactly the thing segment tree revolves around. I mean, for the Q i practiced, deciding what to store in nodes and how to extract answer from it is all the Q proved to be about.

I suppose you have already tried the Q of type -

  1. Minimum value in given range
  2. Maximum value in given range
  3. Sum of given range

If not, try these ones first, as these are the basic “cakewalk” ones in this category. Also, why dont you try Chef and Subarray from May long? Its a very good question on segment trees to practice. I recommend you solve it, and when you get stuck, you can ask in this thread for explanations. It will be a good Q to discuss, but see if you can solve it in one go.

4 Likes
3

Try solving these problems :

All of these have something nice in common that you can apply for problems of this kind. Also, read these to learn about different variations that you might have to use based on the problem:

http://e-maxx.ru/algo/segment_tree

Here’s a list of problems that I found:

2 Likes
4

Yaa, I already solved questions like find min. value, max. value in a given range.I will give a try to Chef and subarray for sure.

5

Give it a try. It is also on easy side, but its a starter where you need to figure out what to store.

1 Like
6

I found SPOJ GSS1 and Frequent to be good conceptually. If you know what to include in node, you will find all problems are solved with almost same algo.

1 Like
7

thanks for the contribution.

1 Like
8

The basic concept is that, the values stored must be such that parent and child nodes are correctly related. If you feel GSS1 taught you correct concepts, test them by attempting problem- SPOJ Frequent