You are not logged in. Please login at www.codechef.com to post your questions!

×

Segment Tree - Lazy Propagation

Can anybody tell me for which type of range query we can apply lazy propagation on segment tree ?Like
I was Just Solving SPOJ Problem GSS4 where I have to modify number in given interval to the floor of it's square root,so can I apply lazy propagation on this type of query . If yes ! then How ?.Thanks in Advance

asked 10 Jun '17, 20:51

am10's gravatar image

5★am10
455
accept rate: 0%


Generally, lazy propagation is used when the number of nodes in the tree that will be affected by a query is large. eg. Adding a number 'v' to every position in the range. But this doesn't mean that you can use this in all problems of this kind. In the example that I mentioned above, you're able to use lazy propagation only because, when an update query appears, you know that for a node that contains 'x' elements, you will add x*v to that node, ie. this update does not depend on the 'x' individual numbers in the range.

That is not the case with this problem, suppose that a node has the sum of a few numbers, when an update query appears, you need to apply square root to all the numbers in the range, and get the new sum. You cannot do this without actually looking at every number in the range.

You can solve this problem by maintaining the minimum and sum in the range, and whenever an update query appears, you simply go to the bottom of the tree, and apply the square root to every individual number, but with a small condition, you will only update a node when the smallest number in its range ie., minimum is more than 1.This way, every node will be visited at most LgLgA (A is the largest number in the input) times, because if you apply square root to any number that many times, it will reach 1. This should be fast enough to get accepted.

link

answered 10 Jun '17, 21:30

hemanth_1's gravatar image

6★hemanth_1
1.4k11
accept rate: 27%

1

Thanks! for your quick and clear response..

(10 Jun '17, 21:45) am105★

Finaly i completed my implementaiton of the SPOJ GSS4 but I am getting TLE..Can you point out where i am making mistake .Here is my code link http://ideone.com/7WZFKN

(11 Jun '17, 13:08) am105★
link

answered 11 Jun '17, 13:24

natsudragneel's gravatar image

1★natsudragneel
393
accept rate: 0%

link

answered 11 Jun '17, 18:14

vikasmagar512's gravatar image

0★vikasmagar512
11
accept rate: 0%

link

answered 11 Jun '17, 18:27

vikasmagar512's gravatar image

0★vikasmagar512
11
accept rate: 0%

link

answered 11 Jun '17, 18:49

coolsagarpawar's gravatar image

0★coolsagarpawar
-11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×668
×155
×102

question asked: 10 Jun '17, 20:51

question was seen: 630 times

last updated: 11 Jun '17, 18:50