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

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.

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!!

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

Ok, I got you but my case is different and my case would not work for the given constraints.