As such i know Segment Tree implementation of variants and have implemented it half dozen times ,still Segment Tree has become a problem which i am getting WA continously in general . How do you give a shot to debugging segment tree solution in general ?
Also every blog i read about Segment Tree ,they pictured Segment Tree of 2^n elements which is simple but i really dont know how to picture up Segment Tree formed out k nodes where k!=2^n :/ Can leafs of such a tree be at different heights ? I mean when i print out my ST linearly is it necessary for leaves to be in same order as the original array from which i constructed segment tree?
Thnksy in adv ^_^
Well, you can imagine like the array has size 2^k, where k is smallest integer so that 2^k>=n, and build a tree over that array, added elements should be ones that wont affect result in any of tree nodes(ones for multiplying, zeros for adding, INFs for minimums and etc), after that, every leaf will be on same depth so outputting and debugging should be easier.
BTW, it's usually not important what numbers to put in new lists, because you just don't use their value (except for the cases when you use value in root)
Well if you are confident about your segment tree code, you shouldn't have much trouble with wrong answers unless you have a conceptual error. Mainly bugs in segment tress occur during lazy propogation. It is important to double check how you are calling ranges ( using inclusive or exclusive). Also I like to add in an extra method to propagate all the lazy fields down the tree in case some values did not propogate.