java - 更新给定范围的数组值

Question

已经给定了一个最初有一些 Max.val 值的数组，然后有查询在范围 L,R 中进行更新，这样任何位置的值都是最小的。例如:

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;

在上述查询之后，我必须显示我的最终 array:i.e 2 1 1 1 Max.val

我正在使用线段树来解决这个问题，但是我遇到了 TLE(超出时间限制)。我不知道为什么？ 我的方法是 logN。这是我的更新功能

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

约束:

N<=10^5;
Q<=10^5;
1<L<=R<=10^5

我做错了什么或者有更好的方法吗？调用函数:

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

您的方法不是 O(log n)，因为要从 L 更新到 R，您至少必须更新 L 和 R 之间的所有位置 (T[curr] = Math.min(T[curr] , c)).

要真正实现 O(log n) 更新，您必须实现 segment tree with lazy propagation .该结构的要点是避免更新每个位置。每当遇到覆盖整个范围的递归更新时，不要马上更新，只需将范围节点标记为稍后更新即可。并且在更新(或查询)时，在需要时传播计划的更新(当查询或更新仅覆盖范围的一部分并且您需要更深入时)。