Segment Tree Persistency on Lazy Updates Part 2

Introduction

In the previous lecture, we used persistence together with lazy propagation in a way that avoided real pushing. For range addition and range sum queries, a query could carry accumulated lazy values from ancestors, so old child nodes did not always need to be updated physically.

This lecture is about the next case: sometimes that trick is not enough. We now study a persistent lazy segment tree where we really need $\operatorname{push}$ lazy information into children.

The example operation is range assignment:

Create a new version by setting every element in $[l, r]$ to $y$ , and answer range sum queries in any version.

The new difficulty is not persistence itself. Students already know that each version is represented by a root and that unchanged nodes are shared. The new difficulty is this:

If a node has a pending assignment and we need to update only part of it, the children must first receive that assignment. But because old versions may share those children, we must copy them before pushing.

Problem or motivation

We have an array $a_{1},_{}$ . Version is the initial array.

#include <bits/stdc++.h> using namespace std; struct Node { int L; int R; long long sum; long long lz; bool has; Node() { L = 0; R = 0; sum = 0; lz = 0; has = false; } Node(long long x) { L = 0; R = 0; sum = x; lz = 0; has = false; } }; int n, q; vector<long long> a; vector<Node> t; vector<int> root; long long comb(long long x, long long y) { return x + y; } int new_node() { t.push_back(Node()); return (int)t.size() - 1; } int clone(int x) { t.push_back(t[x]); return (int)t.size() - 1; } int build(int l, int r) { int x = new_node(); if (l == r) { t[x] = Node(a[l]); return x; } int m = (l + r) / 2; t[x].L = build(l, m); t[x].R = build(m + 1, r); t[x].sum = comb(t[t[x].L].sum, t[t[x].R].sum); return x; } void pull(int x) { t[x].sum = comb(t[t[x].L].sum, t[t[x].R].sum); } void apply(int x, int l, int r, long long y) { t[x].sum = y * (r - l + 1); t[x].lz = y; t[x].has = true; } void push(int x, int l, int r) { if (!t[x].has || l == r) { return; } int m = (l + r) / 2; t[x].L = clone(t[x].L); t[x].R = clone(t[x].R); apply(t[x].L, l, m, t[x].lz); apply(t[x].R, m + 1, r, t[x].lz); t[x].lz = 0; t[x].has = false; } int upd(int x, int l, int r, int tl, int tr, long long y); void upd_owned(int x, int l, int r, int tl, int tr, long long y) { if (l == tl && r == tr) { apply(x, l, r, y); return; } bool pushed = t[x].has; if (pushed) { push(x, l, r); } int m = (l + r) / 2; if (tl <= m) { if (pushed) { upd_owned(t[x].L, l, m, tl, min(m, tr), y); } else { t[x].L = upd(t[x].L, l, m, tl, min(m, tr), y); } } if (tr > m) { if (pushed) { upd_owned(t[x].R, m + 1, r, max(m + 1, tl), tr, y); } else { t[x].R = upd(t[x].R, m + 1, r, max(m + 1, tl), tr, y); } } pull(x); } int upd(int x, int l, int r, int tl, int tr, long long y) { if (tl > tr) { return x; } x = clone(x); upd_owned(x, l, r, tl, tr, y); return x; } long long get(int x, int l, int r, int tl, int tr) { if (tl > tr) { return 0; } if (l == tl && r == tr) { return t[x].sum; } if (t[x].has) { return t[x].lz * (tr - tl + 1); } int m = (l + r) / 2; return get(t[x].L, l, m, tl, min(m, tr)) + get(t[x].R, m + 1, r, max(m + 1, tl), tr); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; a.assign(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; } t.reserve(n + q * 40 + 5); t.push_back(Node()); root.push_back(build(1, n)); while (q--) { int type; cin >> type; if (type == 1) { int v, l, r; long long y; cin >> v >> l >> r >> y; root.push_back(upd(root[v], 1, n, l, r, y)); } else { int v, l, r; cin >> v >> l >> r; cout << get(root[v], 1, n, l, r) << '\n'; } } return 0; }

Segment Tree Persistency on Lazy Updates Part 2

Introduction

Problem or motivation

What is new compared to the previous lecture

Core concept

Main algorithm

Implementation

Complexity