What is the approach to solve this segment tree problem?
https://hack.codingblocks.com/contests/c/547/725
My approach was to store the binary representation in a string at every node. (I think this’ll give TLE)
Is there any better approach?
If you are worried about time because of concatinating two strings at each node ( and if you belive it takes O(n) time ) , You should probably read about
Merge sort tree
It uses similar concep like you are using, where a vector is stored at each node, which is formed by merging two vectors of corresponding child. Here is the link for reference, which states time complexity to create such a tree is Nlog(N) and query log(N).
1 Like
This also has updates. do you think it’ll work?
yes, I don’t think there is any reason for this not to work ( if implementation is correct )
What’s the point of sorting here?
can you tell me how to derive the parent from it’s children efficiently?
I think you misunderstood my point. I used merge sort tree just to explain you that your solution too would have the same time complexity as you are doing similar steps. You don’t have to use merge sort tree here though.