c - 2 つ以上のタイプのクエリに遅延伝播を使用する

Question

4 つのタイプの多くのクエリに関する質問があります。

1. 範囲に追加します。

2. 範囲を初期化します。

3. 範囲をスカラーで乗算します。

4. ある範囲で現在の合計を見つけます。

膨大な数のクエリがあるため、遅延伝播でセグメント ツリーを使用する必要がありますが、2 種類以上のクエリで遅延伝播を使用する方法に行き詰まっています。後で更新が行われるときに、どのタイプの更新 (つまり、加算、乗算、初期化) が行われるかをどのように識別できますか?

Answer 1

1.2.3. これは単純な初期化と更新の部分です。

struct info
{
    int prop,sum;
} tree[mx*3];

void update(int node,int b,int e,int i,int j,int x)
{
    if (i > e || j < b) return;
    if (b >= i && e <= j)
    {
        tree[node].sum+=((e-b+1)*x);
        tree[node].prop+=x;
        return;
    }
    int Left=node*2;
    int Right=(node*2)+1;
    int mid=(b+e)/2;
    update(Left,b,mid,i,j,x);
    update(Right,mid+1,e,i,j,x);
    tree[node].sum=tree[Left].sum+tree[Right].sum+(e-b+1)*tree[node].prop;

}

4.これはクエリ部分です：

int query(int node,int b,int e,int i,int j,int carry=0)
{
    if (i > e || j < b) return 0;

    if(b>=i and e<=j) return tree[node].sum+carry*(e-b+1);

    int Left=node<<1;
    int Right=(node<<1)+1;
    int mid=(b+e)>>1;

    int p1 = query(Left, b,mid, i, j, carry+tree[node].prop); 
    int p2 = query(Right, mid+1, e, i, j,carry+tree[node].prop);

    return p1+p2;
}

そしてからmain

update(1,1,number_of_element,first_range,last_range,value);
query(1,1,n,first_range,last_range);

ここで、tree はセグメント ツリーです。すべてのノードには 2 つの情報が含まれます。1 つは、前に追加した番号です。prop はその履歴を保存します。sum はそのノードの合計値です。

**あなたのコメントの後:

//Initialization:

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }
    int Left=node*2;
    int Right=node*2+1;
    int mid=(b+e)/2;
    init(Left,b,mid);
    init(Right,mid+1,e);
    tree[node]=tree[Left]+tree[Right];
}