c - 对超过 2 种类型的查询使用延迟传播

Question

我有很多查询的问题，有四种类型：

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 是段树。每个节点将包含两个信息。一个是您之前添加的号码。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];
}

Answer 2

你可以给更新函数另一个参数，称之为查询。根据该参数的值，完成相应的操作。

对于加法和乘法，惰性传播的信息可以包含在两个字段中：

令 A 为叶子的初始值，并且存在任意一系列乘法和加法，例如：+u +v *w +x *y +z。在lazy1 上应用这些操作。所以它的值是：((u+v) * w +x) * y + z。lazy2 应该只包含乘法，这将是 w * y。

要更新节点，首先乘以lazy2，然后添加lazy1。

原因：对初始值 A 进行运算，得到：A * w * y + ((u+v)*w +x)*y + z。很简单，只有乘法直接影响初始值 A。因此，这些可以存储在一个字段中，而另一个字段可以包含加法，并且必须对其应用乘法，因为这里的顺序很重要。