arrays - 更新が均一でない場合のセグメント ツリーの遅延伝搬最大クエリ

Question

セグメント ツリーの遅延伝播の問題に直面しています。私は配列A、長さ N 、より小さい配列 (最大長 20) を持っています。また、配列Aiで現在指しているインデックス i を参照する、インデックスBの配列もあります。

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

これらは、非常に単純な形式の 2 つの方法です。ただし、入力の制約が大きいため、O(logn) クエリと更新時間が必要です。そのため、セグメント ツリーを使用することを考えました (現在、複雑さは O(n^2) です)。遅延伝播で中間ノードを更新します。

どんな洞察も役に立ちます。また、同様の問題をオンラインでリンクできる場合は、私ができなかったので本当に役に立ちます（これはどのWebサイトからのものでもないため、そのようなものは知りません）。助けてくれてありがとう。

注: その場合は 1b[i]>a[i].lengthに置き換えa[i][b[i]]ます。