Please Don’t Skip this question. You were also a newbie programmer once.
I want to know what topics (Data Structures) i need to learn in an order to solve DRGDEN.
- I’ve learnt about segment trees that is basic range sum and minimum query and updates and lazy propagation, i know graphs, trees and basics of them.
- when i saw the editorial i saw many terms like tree flattening, bit tree, fenwick trees, etc, etc
- some people have solved it using segment trees but i could not understand their hundred’s of lines of code
- Please leave below your thoughts on topics need based on how you solved
- if possible leave your code link and some resources
Doesn’t the editorial tell you the exact topics you need to know?
I was so confused i could not figure out the order in which i need to study things sir.
Please Help me. I just know the basics of seg tree and lazy.
I need some guidance from this enormous community
Why does there have to be an order?
sir i really don’t understand what you’re even asking. 
.
I was just seeking some help as i could’nt figure out reading tree flattening or fenwinck tree or seg tree or some of them in an order. i was just seeking help. because many ppl solved in different ways
The editorial of the problem actually does look pretty good but I understand that it can still be overwhelming for people. To solve this problem, you must first understand the editorial until the point where they convert the problem into finding sums on path in a tree. That part does not require any fancy data structure and with just that you can solve the problem for 55 points.
Before moving forward, you must need the knowledge of Depth First Search and either one of segment trees or Fenwick trees.
As the editorial has mentioned afterwards, there are multiple ways to calculate sum queries on a path in a tree. One way is the tree flattening trick and then using a segment/Fenwick tree on the flattened tree. This way is also explained very well in the editorial itself. Once you understand segment/Fenwick tree and Depth First Search, you should be able to understand the complete solution in the editorial.
The other way is using Heavy-Light Decomposition which can be a bit more overwhelming for people to learn and is a bit trickier to code. But you don’t necessarily have to learn it to solve this particular problem.
Just remember that even the best editorial (for a problem which is one level over your current level) is not a piece of cake to understand. You have to think about and make sense of each line before moving forward.
Good luck!
for dragon den.You must know about
- Fenwick Binary Indexed Tree.
2.Segment Tree
3.Stock Span Problem(finding next and previous greater element)
I used a bit different approach. I used heavy-light decomposition on tree.
here is the link for my submission.
You can also find a nice blog on heavy light decomposition here
Thanks a lot Sir. Feeling nice to get support from the same person on Quora and Codechef
Hello @engineerman I’ll tell you about how I solved that problem.
Fortunately before Long Contest I was learning Segment Trees to improve my algorithmic skills.
And I think you just need a basic understanding of Segment Tree to solve that problem ofc also lazy propagation.
At first you may find Segtree hard but believe me stick to it for a while try hard to understand what is start, end, node in the parameters you’ll find Segtree very easy.
I’ll suggest you to watch Code N Code video on Segment trees.
and I don’t know it was my luck or not but I watched one video on Nearest Greater Element using Stack by Aditya Verma.
That’s All in the long contest I was able to use these concept and there was a time when I was Rank 5 when I solved that problem.
And don’t get afraid of hundreds of lines. Sometimes those hundreds of lines are easy to understand.