2

我在段树的延迟传播中面临一个问题。我有一个数组A，长度为 N ，较小的数组（最大长度为 20）。我还有一个索引数组B ，指的是我当前在数组Ai中指向的索引。

有 2 个操作，： a) 更新B的指针以指向给定范围的下一个元素。b) 打印给定范围内指针当前指向的最大值。

例如：-

 int[][] array=
{
    {1,2,3,4},
    {8,4,0,0},
    {3,4,2,5}
};
int[] B={1,1,1};

在查询范围 1,2 时，最大值为 8。这是因为数组 B 的指针指向数组的第一个元素。所以我们正在使用 1,8。

在进行 2,3 max =8 的查询时；这是因为我们正在使用值 8,3。一般来说，

int max(int[][] arr,int[] b,int l,int r){ 
    int max=0;
    for(int i=l;i<=r;i++){
        max=Math.max(max,arr[i][b[i]]);//using java Math class here
    }
    return max;
}
void update(int[] b,int l,int r){
    for(int i=l;i<=r;i++){
       b[i]++; 
    }
}

这是非常简单的两种方法。但是，由于输入限制较大，我需要 O(logn) 查询和更新时间。这就是为什么我想到使用段树的原因（目前它的复杂性是 O(n^2)。但是我似乎无法弄清楚如何更新延迟传播中的中间节点。

任何见解都会有所帮助。另外，如果您可以在线链接任何类似的问题，那将非常有帮助，因为我做不到（我不知道这样的问题不是来自任何网站）。感谢您的任何帮助。

注意：如果b[i]>a[i].length然后替换a[i][b[i]]为 1。

4

0 回答 0