Stack Overflow
Stack Overflow

Questions tagged [lazy-propagation]

16 questions
4
votes
1 answer

Segment Tree with lazy propagation Time limit problem

The following is the implementation of http://www.spoj.pl/problems/LITE/ using Segment Tree's with lazy propagation. I am new to segment trees and I cannot understand why I am getting TLE. Could someone please look at it and help me correct my…
Ronzii
  • 247
  • 1
  • 3
  • 12
3
votes
2 answers

How is it possible to apply the lazy approach to update a segment tree if the update is more complex than simple addition or multiplication?

Consider this question. In this segment tree solution, we are updating all nodes of the tree in the given range. Is it possible to apply lazy propagation to this problem? Edit: Consider that in every update operation arr[i] = (1-(1-arr[i])*a),…
yobro97
  • 1,125
  • 8
  • 23
3
votes
3 answers

Lazy propagation in segment tree?

Well, I was trying to solve this Flipping coins problem on Codechef. Am solving it with segment trees. But getting time limit exceed. I searched and found that I have to use lazy propagation. But I am unable to understand. My update function works…
dejavu
  • 3,236
  • 7
  • 35
  • 60
2
votes
0 answers

Segment tree lazy propagation max query when update is non uniform

I am facing a problem in lazy propagation of segment tree. I have an array A, of length N ,of smaller arrays (of max length 20). I also have an array of indices B, referring to the index i am currently pointing to in the array Ai. There are 2…
Rajarshi basu
  • 330
  • 1
  • 10
2
votes
1 answer

Lazy Propagation - HORRIBLE spoj

I am attempting the problem HORRIBLE from spoj and here's the link: http://www.spoj.com/problems/HORRIBLE/ I am trying to teach myself lazy propagation with segment tree. Following is the code I have written, I have tried to make it as concise and…
Pranav Arora
  • 993
  • 2
  • 10
  • 16
1
vote
0 answers

lazy propagation in segment tree when two changes could not be combined

Suppose there are two sequences A:a1,a2,...,an and B:b1,b2,...bn ,and we need two operations: 1.sum(i,j):calculate the sum of ai,a(i+1),...,aj 2.range_add(i,j):range modify the sequence A in [i,j] , with…
li yixiao
  • 59
  • 4
1
vote
1 answer

Why a second depth first search?

Recently I came accross a problem called Gravity Tree I couldn't solve it on my own so I checked the editorial. The authors solution was to dfs over the vertices once and form a segment tree.where each node contains the distance from the vertice to…
Harry Jobs
  • 11
  • 2
1
vote
2 answers

Using lazy propagation for queries of more than 2 types

I have a question with a lot of queries which are of four types: Add to range. Initialize a range. Multiply a range with scalar. Find running sum over a range. Since queries are in huge numbers I have to use segment tree with lazy propagation but…
user3933528
  • 123
  • 2
  • 10
1
vote
1 answer

Lazy Propagation

I was solving GSS3 in spoj using lazy propagation in segment trees.I referred to this blog : Lazy Propagation How should i proceed in this question using lazy propagation and i couldn't understand how lazy array is being used in this…
Drave
  • 27
  • 5
1
vote
2 answers

Segment tree with lazy propagation for multiple of 3

Abridged problem: You're given an array of n elements, initially they are all 0. You will receive two types of query: 0 index1 index2, in this case you have to increase by one all elements in range index1 index2(included). Second type: 1 index1…
emacoder
  • 11
  • 1
  • 5
0
votes
0 answers

Lazy Propagation On Skiplist

Is there anyone who tried lazy propagation on SkipList? Or is it reduce time complexity for priority queue? I am quite familiar with segment tree lazy propagation optimization. But I am thinking is it same beneficial for Skiplist? If we add an…
Sabbir Pulak
  • 9
  • 2
0
votes
1 answer

Lazy propagation range update

I was reading lazy propagation on GFG and it says following for range update For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we…
aditya rai
  • 67
  • 6
0
votes
0 answers

Can Lazy propogation be implemented for division queries?

How can lazy propogation be implemented for segment tree in which we have two types of queries, one for finding maximum element in a given range and other is to divide elements in a given range by a number( not necessarily same for all elements like…
swap96
  • 75
  • 1
  • 1
  • 11
0
votes
1 answer

Lazy update on Segment tree

Im having a problem which need a structure that can handle 2 operations: Change values of nodes from position x to position y to newValue. Get the sum of values from position a to b. The number of nodes is 50000 and number of queries is 50000. Im…
Minh Nguyen Duc
  • 1
0
votes
1 answer

Element rotation in segment tree

Given an array A with N numbers(all positive and contain less than or equal to 4 digits), 2 types of queries are to be supported. There are total M queries. Update a range given by indices L,R(both inclusive) by K. Return the maximum element in a…
gaurav1199
  • 17
  • 4