Ответ 1
Я сравню ленивую операцию обновления с обычной операцией обновления и как это изменит операцию запроса.
В обычной операции с одним обновлением вы обновляете корень дерева, а затем рекурсивно обновляете только нужную часть дерева (тем самым предоставляя вам скорость O(log(n))). Если вы попытаетесь использовать ту же логику для обновления диапазона, вы можете увидеть, как она может ухудшиться до O(n) (рассмотрите очень широкие диапазоны и посмотрите, что вам в основном нужно будет обновлять обе части дерева).
Итак, для преодоления этой идеи O(n) необходимо обновить дерево только тогда, когда оно вам действительно нужно (запрос/обновление в сегменте, который был ранее обновлен, что делает ваши обновления ленивыми). Итак, вот как это работает:
- создание дерева остается абсолютно одинаковым. Единственное незначительное отличие состоит в том, что вы также создаете массив, который содержит информацию о потенциальных обновлениях.
- когда вы обновляете node дерева, вы также проверяете, нужно ли его обновлять (из предыдущей операции обновления), а если оно есть - вы обновляете его, отмечаете, что дети будут обновляться в будущем и отмените node (ленивый)
- когда вы запрашиваете дерево, вы также проверяете, нужно ли обновлять node, и если это обновление, отметьте его потом и отмените его после.
Ниже приведен пример обновления и запроса (решение запроса максимального диапазона). Для полный код - проверьте эту статью.
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
}
и запрос:
int query_tree(int node, int a, int b, int i, int j) {
if(a > b || a > j || b < i) return -inf; // Out of range
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 >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];
return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j));
}