Menu
have given an array initially having some Max.val value , then there are queries making a update in a Range L,R, such that the value at any position is minimum. For Example:
Update Range 1 3 with value 3
Array 3 3 3 Max.val Max.val
Now update 2 and 4 with 1
Array 3 1 1 1 Max.val
Now update 1 and 2 with 2
Array 2 1 1 1 Max.val
i.e update only if(A[i]>value) A[i]=value;
After the above Query I have to display my final array:i.e 2 1 1 1 Max.val
I am using Segment Tree to solve this Question but I am getting TLE(Time limit Exceeded). I don't know why ? My approach is logN. Here is my update function
public static void lets_change(int curr, int[] T, int x, int y, int a, int b, int c) {
// x=0 and y=n and a=L , b=R and C= Value to be updated
// T contains Integer.Max_value at start
if (x > y || b < x || a > y)
return;
if (x == y) {
T[curr] = Math.min(T[curr], c);
return;
}
lets_change(2 * curr, T, x, (x + y) / 2, a, b, c);
lets_change(2 * curr + 1, T, (x + y) / 2 + 1, y, a, b, c);
T[curr] = Math.min(T[2 * curr], T[2 * curr + 1]);
}
Constraints:
N<=10^5;
Q<=10^5;
1<L<=R<=10^5
What have I done wrong or there is any better way? Call a function:
for(int i=0;i<Q;i++){
int l = in.nextInt()-1;
int r = in.nextInt()-1;
int c = in.nextInt();
lets_change(1,T,0,n-1,l, r,c);
}
624
To update all the elements of an array, call the forEach() method on the array, passing it a function. The function gets called for each element in the array and allows us to update the array's values. Copied! const arr = ['zero', 'one', 'two']; arr.
The process of updating (modifying/changing) an existing element of an array at a specified index with another element is called updating an array or update operation in array.
Set update() in Python to do union of n arrays A simple solution for this problem is to create a empty hash and traverse each array one by one, this hash contains frequency of each element in list of arrays.
In c you can't pass a variable by reference, the array variable that you assign inside the function contains initially the same address as the passed pointer, but it's a copy of it so modifying it will not alter the passed pointer.
Your approach isn't O(log n), since to update from L to R you have at least to update all positions between L and R (T[curr] = Math.min(T[curr], c)).
To really achieve O(log n) updates, you have to implement a segment tree with lazy propagation. The gist of the structure is to avoid updating every position. Whenever faced with a recursive update that covers the entire range, do not update right away, just mark the range node to be updated later. And when updating (or querying), propagate the scheduled updates whenever needed (when the query or update only covers a part of the range and you need to go deeper).
189
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
