This is an answer to @blake_786’s question regarding updates with lazy propagation, since my answer would not fit into a comment.
Persistent Lazy Propagation
Lazy propagation is the act of updating by need. To do lazy propagation with a persistent tree, like for regular segment tree, we flag nodes whenever they need to update and subsequently pass them down to the children after visiting. But the difference is, since we are doing things persistently, we create new nodes during update.
The thing is, propagation varies from problem to problem. Range set-value update is different from range increase, range flip, etc. But the template is similar. Let’s make two arrays, hasflag[] and flag[] to mark if a node has a lazy flag or not. Then the code of persistent propagation will look like the following:
bool hasflag[]; // if node has a flag (sometimes, you can omit this)
int flag[]; // the actual value of the flag
// returns a new node with a lazy flag
int newlazykid(int node, int delta, int L, int R);
void propagate(int p, int L, int R) {
if (hasflag[p]) {
if (L != R) { // spread the laziness
l[p] = newlazykid(l[p], flag[p], L, M);
r[p] = newlazykid(r[p], flag[p], M + 1, R);
}
// reset flag
hasflag[p] = false;
}
}
The propagate() method spreads the laziness from parent to children. In doing so, we update the values of the children depending on our flag. But if you notice, we want persistence so the way to update this is to create “new lazy kids” during propagation. (Note, we don’t need to create a “new non-lazy parent” node after propagation, since it’s the same parent that was just too lazy to update).
Lazy Children
To propagate properly, we need a way to create lazy child nodes. That’s what the newlazykid() method is for. I left it blank since the propagation style largely depends on the problem. But by default, the lazy kid should make a new cloned node, update it, then setup its flags. Here’s an example template code:
int newlazykid(int node, int delta, int L, int R) {
int p = ++NODES;
l[p] = l[node];
r[p] = r[node];
flag[p] = flag[node]; // need this since lazy kid might be lazy before
hasflag[p] = true;
/* range increase */
flag[p] += delta;
st[p] = st[node] + (R - L + 1) * delta;
/* edit depending on the problem */
return p;
}
After setting up flags, the child needs to know what needs to change based on the flag. It depends on the problem. For example, for range increase the kid can have value st[node] + (R - L + 1)*delta. If it’s range set-value we simply make the kid have value delta, if it’s range minify the value is min(st[p], delta) and so on.
Lazy Range Update/Query
Now that we have propagation, how does the final range update code look like? It’s amazingly succint if you ask me 
// range update on [a:b] with value x, on the tree rooted at p
int update(int a, int b, int x, int p, int L=0, int R=n-1) {
if (b < L || R < a) return p;
if (a <= L && R <= b) return newlazykid(p, x, L, R);
propagate(p, L, R); // always do this before going down
return newparent(update(a, b, l[p], x, L, M),
update(a, b, r[p], x, M + 1, R));
}
Now, every time we query down we should also propagate. We’ll achieve very similar code after.
// range query on [a:b], on the tree rooted at p
int query(int a, int b, int p, int L=0, int R=n-1) {
if (b < L || R < a) return 0;
if (a <= L && R <= b) return st[p];
propagate(p, L, R); // always do this before going down
return query(a, b, l[p], x, L, M) + query(a, b, r[p], x, M + 1, R);
}
Hope that was helpful. I’d like to have your thoughts on this.
