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

我有一个问题,有很多查询,有四种类型:

  1. 添加到范围。

  2. 初始化范围。

  3. 用标量乘以范围。

  4. 查找范围内的运行总和。

由于查询数量巨大,我必须使用具有延迟传播的分段树,但我仍然坚持如何在超过2种类型的查询上使用延迟传播。 如何在以后进行更新时识别出哪种更新(即添加,乘法,初始化)?

你可以给Update funtcion另一个参数,称之为Query。 根据该参数的值,完成相应的操作。

对于加法和乘法,延迟传播的信息可以包含在两个字段中:

设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是微不足道的。 因此,这些可以存储在一个字段中,而另一个字段可以包含添加,并且还必须在其上应用乘法,因为这里的顺序很重要。

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

这里,树是段树。 每个节点都包含两个信息。 一个是你之前添加的数字。 道具将存储该历史。 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]; }