Изменить ленивое распространение в сегментном дереве
Недавно я читал о ленивом распространении в сегментном дереве и тоже его кодировал. Но я застрял, когда вместо добавления значения (= 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
}
Решение
HINTS
Предположим, вам нужно разделить на фиксированное значение 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)
Другие решения
Других решений пока нет …