Segment Tree

I was reading segment tree from https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/

there is one function (without lazy propagation)

void updateRange(int node, int start, int end, int l, int r, int val)

{

}

Can anyone explain its run time complexity ?

i guess its (R-L)logn if i am right why should one use this function instead of regular update

This implementation helps when you have a long range of updates to make. That way, if you use regular update you have to traverse log(n) depths each time going down and then again up the tree (totalling to around 2*log(n) levels).

Instead if you use the range update, the function is implemented in such a way that you don’t traverse 2*log(n) for each leaf update. Rather while returning from leaf on the way up, the range update checks if the non-leaf nodes contain updatable leafs and if yes, again traverses down for updating those leafs. Thus although asymptotically the runtime is same for both regular and range updates, the constant factor in asymptotic runtime of range update is less.

I think the complexity given in the article is wrong. It should be O(N). The reason for that is, in a segment tree there are atmost 2*N-1 nodes. If we update from 0 to N-1 it will traverse 2*N-1 nodes, so the complexity will be O(N). Mathematically,

Recurrence for updateRange without Lazy is: T(N) = 2*T(N/2) + O(1) = O(N)
So, time complexity of update should be O(N).
I will update it as soon as possible. Thanks for pointing it out :slight_smile:

1 Like

@r3gz3n
1)At most 4*N space is needed to build a segment tree, if you are using a linear array to implement it.

  1. if we update from 0 to N-1 it will take O(NlogN) time and not O(N)

Read the @brijs comment, and read this to know why segment tree needs O(4*N) space –
Quora

true its move to depth of nlogn in each call but at the end it updates (R-L) leaf nodes + some internal nodes so i think its order is greater than O(N) @brijs

While updating we will visit each node twice (once when we are going down and once when we are coming up). So even if we consider O(4*N) space it will take O(N) time. That function will work similar to build function which also take O(N) time.

1 Like

@nil96 could you please upvote if this was helpful