отображение данных и ленивое распространение в дереве сегментов

Я буду сравнивать ленивую операцию обновления с обычной операцией обновления и то, как это меняет операцию запроса.

В обычной одиночной операции обновления вы обновляете корень дерева, а затем рекурсивно обновляете только необходимую часть дерева (что дает вам скорость O(log(n))). Если вы попытаетесь использовать ту же логику для обновления диапазона, вы увидите, как она может ухудшиться до O(n) (рассмотрите очень широкие диапазоны и убедитесь, что вам в основном потребуется обновлять обе части дерева).

Таким образом, чтобы преодолеть эту O(n) идею, нужно обновлять дерево только тогда, когда оно вам действительно нужно (запрос/обновление в сегменте, который был ранее обновлен, что делает ваши обновления ленивыми). Итак, вот как это работает:

• создание дерева остается абсолютно таким же. Единственное незначительное отличие состоит в том, что вы также создаете массив, содержащий информацию о потенциальных обновлениях.
• когда вы обновляете узел дерева, вы также проверяете, нужно ли его обновлять (из предыдущей операции обновления), и если да, то вы обновляете его, отмечаете дочерние элементы для обновления в будущем и снимаете пометку с узла (ленивый)
• когда вы запрашиваете дерево, вы также проверяете, нужно ли обновлять узел, и если это так, обновите его, отметьте его дочерние элементы и снимите отметку впоследствии.

Вот пример обновления и запроса (решение запроса максимального диапазона). полный код — см. эту статью.

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

Когда вы запрашиваете узел в дереве сегментов, вам необходимо убедиться, что все его предки и сам узел правильно обновлены. Вы делаете это при посещении узлов запросов.

При посещении узла запроса вы проходите путь от корня к узлу запроса, заботясь обо всех ожидающих обновлениях. Поскольку вам нужно посетить O (log N) предков, для любого заданного узла запроса вы делаете только O (log N) работы.

Вот мой код для дерева сегментов с ленивым распространением.

// interval updates, interval queries (lazy propagation)  
const int SN = 256;  // must be a power of 2

struct SegmentTree {

    // T[x] is the (properly updated) sum of indices represented by node x
    // U[x] is pending increment for _each_ node in the subtree rooted at x 
    int T[2*SN], U[2*SN];

    SegmentTree() { clear(T,0), clear(U,0); }

    // increment every index in [ia,ib) by incr 
    // the current node is x which represents the interval [a,b)
    void update(int incr, int ia, int ib, int x = 1, int a = 0, int b = SN) { // [a,b)
        ia = max(ia,a), ib = min(ib,b); // intersect [ia,ib) with [a,b)
        if(ia >= ib) return;            // [ia,ib) is empty 
        if(ia == a && ib == b) {        // We push the increment to 'pending increments'
            U[x] += incr;               // And stop recursing
            return; 
        }
        T[x] += incr * (ib - ia);          // Update the current node
        update(incr,ia,ib,2*x,a,(a+b)/2);  // And push the increment to its children
        update(incr,ia,ib,2*x+1,(a+b)/2, b);
    }

    int query(int ia, int ib, int x = 1, int a = 0, int b = SN) {
        ia = max(ia,a), ib = min(ib,b); //  intersect [ia,ib) with [a,b)
        if(ia >= ib) return 0;          // [ia,ib) is empty 
        if(ia == a && ib == b) 
            return U[x]*(b - a) + T[x];

        T[x] += (b - a) * U[x];           // Carry out the pending increments
        U[2*x] += U[x], U[2*x+1] += U[x]; // Push to the childrens' 'pending increments'
        U[x] = 0;

        return query(ia,ib,2*x,a,(a+b)/2) + query(ia,ib,2*x+1,(a+b)/2,b);
    }
};