I know that construction of segment trees takes O(n) time but if in segment tree each node is itself an array and I have to update the array. This would take time O(n*A) time where A is length of array. Am I correct? That means construction is costly. Will segment fail or I should change my implementation?
Any help would be appreciated.
Construction of segment tree takes O(nlog(n)) i think
If each node is an array, then i think you mean Merge sort tree
2 Likes
Actually, I learnt segment tree from a question which is min range query and there it was O(n) for construction… not sure about merge sort tree!!
I think I was not clear with the question…what I actually meant is that during construction of segment tree I have to fill nodes in segment tree and node is an array itself that during each filling of node I have to traverse the array(which is node of seg tree). So for each node I have to traverse the array, so It would take O(n*A) time.
I am not talking about updating any range of segment tree.
You don’t need to store the whole array in a node. While querying you need to merge the two left and right node to get the whole array at that time.
1 Like
No, I learnt basic RMQ where node was a single entity but now the I have a different scenario with me where each node is an array!!
Ok, I’ll try to learn about merge sort tree then !! 
Thanks!!
2 Likes
The size of each array need not be n. it will be n/(2^h) so it will take only O(nlogn) even if it’s an array…just like it happens in merge sort
1 Like
Ok, I got you but my case is different and my case would not work for the given constraints.