Segment Trees Doubt

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.

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


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

I think you are looking for interval trees.

1 Like

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