Can anyone provide good resources to learn segment tree applications in non-classical problems.
I have already understood its working to find maximum/minimum/ sum of a range and point/range updates, lazy propagation.
But the trouble is, that i don’t know how to apply segment tree in other problems, for instance SHTARR of OCT17 (i solved it using sqrt decomposition). I have googled segemnt tree many times, but there i found nothing about its implementation in non-claasical problems…
Any reference, study material/ explanation would be most welcome 
1 Like
Yes, I also need the same ! There are many different applications of segment tree sin a wide variety of questions! Any link would help a lot.
I’m also facing the same problem. Even after learning plethora about segment tree, I don’t know how to apply it to problems which are not straightforward(non-classical).
Segment tree in non classical problem is all based on your thinking and intuition.
Some people feel segment tree isnt possible here, not possible there, is only relevant in questions of queries etc. But people who are deep into this find one way or other out.
Like, consider Sereja and Commands of previous long challenge. I felt Square root decomposition was intuitive and way to go. I was surprised to see people solved it using segment trees! If I am not wrong, I heard that Chef and dishes of this long also has a possible segment tree solution, but I am not sure.
PS: Regarding rating updates, please wait for 1 week at least.
I m sorry for a late answer, I haven’t been active on Discuss lately.
Anyway, the property that you exploit to use a segtree is that “If I know the answer in the range [A, B] and [B, C], can I get the answer for [A, C] fast?” If you can answer this question then go ahead and use a segment tree. Additionally for lazy “If I update a range, can I ‘represent’ the update using just one variable?”. For example, if its range sum+range addition, then you know you can just store the addition update and add (B-A+1) \times \text{Update variable} when answering the query.
One of the slightly non trivial problems is Sereja and Commands. The genius of this segtree solution is that you can use two segtrees, one for commands and one for the array. Executing the commands in reverse order, you know how many times each command was executed and use it on the array segtree. There is no foolproof generalization of thinking about segtree problems but what I told you is applicable to many problems. Other non trivial problems can be solved using your non-intuitive reasoning(Kinda like DP, there is no proper way of thinking about DP problems, each problem is different in its own way).
3 Likes
@ista2000 @vijju123 please help/reply.
PS: Do you know why there is a delay in rating update for OCT17?
1 Like
No problem, I’ll wait for one week… (any particular reason?)
Well, If you have solved any of these problems using segment tree or have any reference or even any commented solution, that would be most welcome.
PS:one glance on problem SHTARR was enough to recognise for me that this problem has two solutions, Segment tree (probably faster) and sqrt decomposition. I happen to recognize segment tree problems at a glance, but recognizing a problem algorithm doesn’t get you anywhere when you don’t know how to implement it in that problem.
For implementation, you will have to pry on other people’s code :3. Well, some coders are generous enough to comment, but most write readable codes which you can understand sooner or later.
Mate, can you explain the segment tree approach for SHTARR problem a bit detailed if u don’t mind, the explanation in official editorial went over my head. I haven’t solved any problem using segtree except the classical ones, perhaps that why…
Possibly accompanied with implementation if you have…
Thanks in advance