Update a value of a Array for a given Range

Question

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);
}

Answer 1

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).