You have an array arr[] containing n elements initially all 0. You need to do a number of update operations on it. In each update you specify l, r and val which are the starting index, ending index and value. We need to update values in that range [l, r] such that arr[i]=max(arr[i], val). No of Queries Will be 10^5 and n will be 10^5 . How do I do it using Segment Trees? Ideas please?
Range updates/queries are handled usually by segment trees with lazy propagation.You’ve only mentioned the update operation. Can you post what the queries ask ?
you can use segment trees with lazy propagation to solve above problem. Google about it to get more information.
Lazy propagation allows you to do range updates and range queries in log(n) time.
you can find a c++ implementation of lazy propagation here
I am guessing, this is what the queries ask -
Query 1 : 1 x y v
Add v to array A to all the indices from x to y, i.e.,
for (i = x; i <= y; i++)Ai += v;Ai %= M;
Query 2 : 2 x y v
Multiply the scalar v with the array A for indices from x to y
for (i = x; i <= y; i++)Ai *= v; Ai %= M
Query 3 : 3 x y v
This implies initializing the array A at all the indices from x to y with the value v
for (i = x; i <= y; i++) Ai = v ;
Query 4 : 4 x y
Find the sum of the values in A from x to y
sum = 0;
for (i = x; i <= y; i++) sum += Ai sum %= M
I must be an astrologer.
I’ve understood what the update operation is. Can you post what the queries ask to answer in L to R ?
@aj95 after all the queries, arr[i] should be accessible with final maximum value. Queries are just for updating.
The problem can be done by segment trees with lazy propagation. If you don’t know about lazy propagation, you can read http://goo.gl/Hxy6wR . When updating you can use
lazy[index] = max(lazy[index],val) when you come across a range that completely lies within L to R. After all Q queries, you can simply access final value at each index by traversing from top to the corresponding leaf node. If I sound confusing, I suggest you read thoroughly about segment trees and lazy propagation.
The line is very thin; asking about a contest problem violates code of conduct, while discussing a related paradigm probably does not ? ON a lighter note, I just found the occasion perfect for that kind of a response , I hope you don’t mind.
PS : There are many online tutorials on lazy propagation. There are also threads available on codechef. All you need is some googling. Rest your palm now, it may be tired :restpalm:.