Lazy Propagation

Lazy propagation extends a segment tree so updates affecting entire intervals can be postponed. Updating every covered leaf would cost linear time. Instead, a fully covered node immediately updates its aggregate answer and records a pending operation for its descendants. A later operation pushes that tag only when it needs to inspect children. This lesson implements adding a value to every element of a range and querying range sums. Lazy tags depend on the update operation; a range-assignment or mixed-operation tree needs different composition rules.

Prerequisites: Segment trees, range sum invariants, recursion.

Build the idea

1. The invariant includes pending work

   tree[p] always stores the correct sum for its interval after all updates affecting it. lazy[p] stores an addition already included in tree[p] but not yet applied to p's children. Therefore the children may temporarily have older sums, which is safe while the parent alone answers a fully covered query. Do not interpret a lazy tag as work missing from its own node.

2. Apply a whole-interval addition

   If an interval has len elements, adding d to every element increases its sum by d*len. apply(p,l,r,d) adds that amount to tree[p] and adds d to lazy[p]. Pending additions compose by ordinary addition: +3 followed by -1 is +2. This algebra is why storing only one tag is sufficient for this operation.

3. Push before descending

   When a partially covered update or query must inspect children, first apply the parent's lazy addition to both children using their interval lengths, then clear the parent's tag. Otherwise the traversal would read stale values. After a partial update, recompute the parent from its now-correct children. A full-cover query simply returns tree[p] without pushing because that sum already includes its tag.

4. Worked example

   Start with [1,2,3,4,5]. Add 10 to [2,4], obtaining [1,12,13,14,5]. The total is 45 and sum(3,5)=32. Add -2 to [1,5], giving total 35. The last addition can remain at the root as one tag until some later query needs a proper subinterval. Deferring work changes when computation happens, not the mathematical array.

5. Where generalization becomes difficult

   For minimum with range addition, a node minimum increases by d rather than d*len. For assignment, a new tag replaces an old assignment; zero cannot mean 'no assignment' because assigning zero is valid. For assignment mixed with addition, composition order matters. Before adapting this program, define precisely what an update does to an aggregate and how two tags combine.

6. Reason about overlapping updates

   Add 4 to [1,3], then 7 to [3,5]. Position 3 receives 11 while positions 1–2 receive 4 and positions 4–5 receive 7. The recursive interval decomposition handles the overlap automatically. A node's pending addition may be propagated and combined with a child's older tag; because additions compose, the result is independent of when either tag was pushed.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
using namespace std;
struct LazyTree{
    int n;
    vector<long long>tree,lazy;
    explicit LazyTree(const vector<long long>&a):n((int)a.size()-1),tree(4*n+4),lazy(4*n+4){
        build(1,1,n,a);
    }
    void build(int p,int l,int r,const vector<long long>&a){
        if(l==r){
            tree[p]=a[l];
            return;
        }
        int m=l+(r-l)/2;
        build(2*p,l,m,a);
        build(2*p+1,m+1,r,a);
        tree[p]=tree[2*p]+tree[2*p+1];
    }
    // Each of the interval's elements receives d; the sum changes by d * length.
    // The tag is already included in this node, but not yet in its children.
    void apply(int p,int l,int r,long long d){
        tree[p]+=d*(r-l+1LL);
        lazy[p]+=d;
    }
    // Send postponed additions to children before any partial descent.
    void push(int p,int l,int r){
        if(l==r||lazy[p]==0){
            return;
        }
        int m=l+(r-l)/2;
        // Both children now include the addition, so clear the parent tag.
        apply(2*p,l,m,lazy[p]);
        apply(2*p+1,m+1,r,lazy[p]);
        lazy[p]=0;
    }
    void add(int p,int l,int r,int ql,int qr,long long d){
        if(qr<l||r<ql){
            return;
        }
        if(ql<=l&&r<=qr){
            apply(p,l,r,d);
            return;
        }
        push(p,l,r);
        int m=l+(r-l)/2;
        add(2*p,l,m,ql,qr,d);
        add(2*p+1,m+1,r,ql,qr,d);
        // Recombine accurate child sums after a partially covered update.
        tree[p]=tree[2*p]+tree[2*p+1];
    }
    long long sum(int p,int l,int r,int ql,int qr){
        if(qr<l||r<ql){
            return 0;
        }
        // This aggregate includes its lazy tag; full coverage needs no push.
        if(ql<=l&&r<=qr){
            return tree[p];
        }
        push(p,l,r);
        int m=l+(r-l)/2;
        return sum(2*p,l,m,ql,qr)+sum(2*p+1,m+1,r,ql,qr);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<long long>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    LazyTree st(a);
    while(q--){
        char op;
        int l,r;
        cin>>op>>l>>r;
        if(op=='A'){
            long long d;
            cin>>d;
            st.add(1,1,n,l,r,d);
        }
        else{
            cout<<st.sum(1,1,n,l,r)<<'\n';
        }
    }
}

Complexity analysis

Build O(n); each range addition and sum query O(log n); storage O(n). Only boundary paths need further subdivision; complete interior intervals stop at their existing aggregate nodes.

Example input and output

n q; n values; A l r delta adds delta throughout inclusive [l,r]; S l r prints its sum. Require n≥1, valid ranges, all arithmetic fitting long long.

Input

5 5
1 2 3 4 5
A 2 4 10
S 1 5
S 3 5
A 1 5 -2
S 1 5

Output

45
32
35

After +10 on positions 2–4 the array is [1,12,13,14,5]. Subtracting 2 from every element reduces the total by 10.

Practical applications

Range increments and totals; interval coverage counters; HLD with path additions; maintaining dynamic statistics under bulk changes.

Check your understanding

What does lazy[p] represent in this program?

Put it into practice

Adapt the tree to range addition and range minimum.