0

我最近阅读了关于线段树中的惰性传播并对其进行了编码。但是当假设我需要除以值而不是添加值(= val)时我被卡住了。怎么做?请帮忙

我的更新功能如下:

void update_tree(int node, int a, int b, int i, int j, int value) { 
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it

if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}

lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j) { // Segment is fully within range
tree[node] += value;

if(a != b) { // Not leaf node
lazy[node*2] += value;
lazy[node*2+1] += value;
}

return;
}

update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child

tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}
4

1 回答 1

0

提示

假设您需要除以 K 的固定值。

一种可能性是将您的数字转换为基数 K 并在每个节点中维护一个数字数组 A[],其中 A[i] 是位置 i 中所有数字的所有较低节点的总数(当被认为是基数 K数字)。

因此,例如,如果 K 为 10,则 A[0] 将存储所有单位的总数,而 A[1] 将存储所有十位的总数。

这样做的原因是它很容易被惰性除以 K,您需要做的就是设置 A[i]=A[i+1] 并且您可以使用与代码中相同的惰性更新技巧。

例子

假设我们有一个数组 5,11,20,100,K 是 10

我们将为包含值的元素 5,11 构造一个节点:

Total = A[1]*10+A[0]*1 with A[1]=1 and A[0]=5+1 (the sum of the unit values)

我们还会有一个 20,100 的节点,其中包含以下值:

Total = A[2]*100+A[1]*10+A[0]*1 with A[2]=1,A[1]=2,A[0]=0

以及整个 5,11,20,100 数组的节点:

Total = A[2]*100+A[1]*10+A[0]*1 with A[2]=1,A[1]=2+1,A[0]=5+1

如果我们想将整个数组除以 10,我们只需更改顶部节点的数组元素:

A=[1,3,6] changes to [0,1,3]

然后我们可以通过计算查询所有节点的总和:

Total = A[2]*100+A[1]*10+A[0]*1 = 0*100+1*10+3*1=13

这与

(5/10=0)+(11/10=1)+(20/10=2)+(100/10=10)
于 2014-01-24T20:12:54.517 回答