In this topic i will explain a very interesting data structure that can be used to solve a specific set of problems. I will start by explaining its definition and the proceeding with an example problem to solve with it.

**Table of contents:**- What is segment trees?
- Order of growth of segment trees operations
- Show me your code
- Lazy propagation
- Sample problems to try
- References

**What is segment trees?**

Segment Trees is a Tree data structure for storing intervals, or segments, It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It only uses O(N lg(N)) storage.

A segment trees has only three operations: build_tree, update_tree, query_tree.

**Building tree:**To init the tree segments or intervals values

**Update tree:**To update value of an interval or segment

**Query tree:**To retrieve the value of an interval or segment

**Example Segment Tree:**

- The first node will hold the information for the interval
**[i, j]** - If i<j the left and right son will hold the information for the intervals
**[i, (i+j)/2]**and**[(i+j)/2+1, j]**

**N**elements is

**[logN] + 1**. Here is how a segment tree for the interval

**[0, 9]**would look like:

**Order of growth of segment trees operations**

**build_tree:**O(N lg(N))**update_tree:**O(lg(N + k))**query_tree:**O(lg(N + k))

K = Number of retrieved intervals or segments

**Show me your code**

**Lazy Propagation**

Sometimes

**a segment tree operation wouldn't survive if the problem constraints is too large, here it come lazy propagation along with the segment tree.**In the current version when we update a range, we branch its childs even if the segment is covered within range. In the lazy version we only mark its child that it needs to be updated and update it when needed.

Note: Read my solution for problem Can you answer these queries I in this article.

Note: Read my solution for problem Can you answer these queries I in this article.

**Sample Problems to try****References**
In lazy's version, i thinks it's better if you replace update tree[2*node] and tree[2*node+1] in 49th, 50th, 80th and 81th line by lazy[2*node] and lazy[2*node+1].

ReplyDeleteIts reason is your query is not really come down to higher level, so lazy[] should be updated

I can't understand you :)

ReplyDeleteSo, in line 80th:

ReplyDeletetree[node*2] += lazy[node]; // Mark child as lazy

tree[node*2+1] += lazy[node]; // Mark child as lazy

=> replaced by:

lazy[node*2] += lazy[node];

lazy[node*2+1] += lazy[node];

It's correct ?

Yes you are totally right :).. thanks for correcting me ;)..

ReplyDeleteThe same at line 49 and 50, updated check it now and tell me :)

ReplyDeletef

DeleteAt lines 72 and 73, shouldn't this be replaced by a lazy[node]? sorry, I am a beginner.

Deleteupdate_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5

ReplyDeleteupdate_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12

update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100

So, The maximum element in the whole array should be 101

and your final array becomes

[6 6 6 6 6 6 6 13 13 13 13 101 101 101 101 101 101 101 101]

but your program gives output as 117 !!!

No it should be 113, however the size of the array needs to be (1+(1<<6)) as it should be 2^(1+lg N)..

ReplyDeleteAlso there was some checks needed to be added in the lazy version.. please check it and get back to me.

Yes your segment tree size should be

ReplyDeleteint x = (int)(ceil(log2(N)))+1;

size = (1 << x);

This one!

Wow! Thanks for this post, it was very helpful! However, I'm trying to implement another update_tree_val function that sets the values from a range to one value. e.g. update_tree_val(3,7,4) would set the range [3,7] to the value of 4. How can I do this using lazy propagation on your tree?

ReplyDeleteThanks

It would be the same but without incrementing..

DeleteThis means in line 48 ,I have to modify it to tree[node] = lazy[node];

Deleteand in line 62, tree[node] = value; ?

This comment has been removed by the author.

ReplyDeletein line 86 it should be

ReplyDeletetree[node] += (b-a+1)*lazy[node];

I think you forgot that query returns maximum from given range

Deletenot the sum of elements of given range

This is true only when your query is range sum and not max range.

DeleteIn order to do the following:

ReplyDelete1.) Add x to A[i], A[i+1],...,A[j]

2.) Output the sum of A[i],A[i+1],...A[j]

I simply replaced max() with sum() however i am not getting the correct answer.

also replace line 48 and 86 by tree[node] += ( b - a + 1 ) * lazy[node];

Deleteand line 62 by tree[node] += ( b - a + 1 ) * value;

This comment has been removed by the author.

DeleteThis comment has been removed by the author.

ReplyDeletein query_tree() method we could have updated the lazy value to the tree before we look for the out of range condition.... it would result in better performance...

ReplyDeleteam i right about it....please correct me if I am wrong!!

Can you please elaborate how to implement DQUERY?

ReplyDeleteThe best link is:

Deletehttp://apps.topcoder.com/forums/;jsessionid=C7BE6D64D8F4953865BCE8B7945FA2F6?module=Thread&threadID=627423&start=0&mc=13#1060242

http://discuss.codechef.com/questions/50866/segment-trees-doubt

ReplyDeleteVery helpful

ReplyDeletewe have to take array size of 2^n for make segment tree of n element array,then how to make segment tree of 30 or greater elements,because 2^30 = 1073741824

ReplyDeletethen how to take array of this larger size for make segment tree,how to implement ?

It should be 2^(1+lg N) not 2^N

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteVery good and nice blog..

ReplyDeleteI am following your code structure in my SG tree implementation :)

This comment has been removed by the author.

ReplyDeleteHey Note: Read my solution for problem Can you answer these queries I in this article.

ReplyDeleteThe article doesn't point to the solution. It's pointing to the problem itself. Please correct it.

The link is now correct, thanks for pointing this out

DeleteWhat is the complexity of updating range

ReplyDeleteYou said O(log(n+k))

But I read somewhere O(log n + k)

See the link

http://en.wikipedia.org/wiki/Segment_tree

Suppose I want to update range(0,N-1)

It works same like "build_tree" but the complexity is different

nice post good writing service for scholarship essays

ReplyDeleteCan you do range multiplication with segment trees?

ReplyDeleteof course. its same as update value with k * x (x is elements in the range)

DeleteHow to initialize values in a range i.e A[i]=x(some integer) using update function in lazy propagation?

ReplyDeleteIf I change

ReplyDelete(2*node)with(2*node+1)and(2*node+1)with(2*node+2)and start the node position with0instead of1.Will there be any changes in the result?Why have you started node of segment tree with1?in 46 line when will a > b condition becomes true?.

ReplyDeletewell i still cant understand the lazy part.....what does the lazy[]array stores ?.......i mean for a particular node

ReplyDeleteI cannot say if I understood Lazy propagation part.

ReplyDeleteGreat Explanation Of Segment trees

ReplyDeleteplease explain more the lazy propagation part i cannt understand it.

i don't understand

ReplyDeletethank u for your post............really helped me...........

ReplyDeleteIf you want to learn this in a real easy way, watch tushar roy's youtube video on segment tree along with this blog post.

ReplyDeleteD-Query can be easily solved using fast io + MO's algorithm...But using BIT is safer to avoid TLE sometimes...Nice Post...!!!

ReplyDeleteThis comment has been removed by the author.

ReplyDeletethe above content you are posted is very nice.

ReplyDeletekapil sharma new show online

kapil sharma show hit

bigg boss season 10 promo

bigg boss season 10 episodes

one night stand sexy pics

Photo of Sunny Leone

good morning images download free

best good morning images

what if i have to update each nodes with different values means i m not updating whole range with unique value

ReplyDeleteWow,,, This is great blog... Thanks for sharing this informative Content here....

ReplyDeleteWe offfers Tree Trimming in Sacramento, Contact us now for Tree Pruning in Sacramento

Source: Best Tree Company in Sacramento www.cisnerostreecare.com

nice :)

ReplyDeletereally helpful one.

Hey, this is a really intuitive post with which i learnt how a segment tree is coded!

ReplyDeleteCould you point to me some links that will explain how the worst case complexity of updating intervals is O(log(N+k))?