Segment Tree Persistency on Lazy Updates Part 1

Introduction

A persistent segment tree is a segment tree where old versions do not disappear. After an update, we create a new version of the array, but all previous versions are still available for queries.

In a normal persistent segment tree, students usually first see point updates. We clone only the nodes on the path from the root to one leaf, and all other nodes are shared between versions.

In this lecture, we go one step further: range updates with lazy propagation. This is useful when we need queries like:

create a new version after adding $x$ to every element in $[l, r]$ ;
ask the sum on $[l, r]$ in any old version.

The important idea is that persistence and lazy propagation can work together, but we must be careful: we are not allowed to modify nodes that belong to old versions.

Problem or motivation

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

1. Build the first version. 1.1. Create the usual segment tree for the initial array. 1.2. Store the root of this tree as version 0. 2. Create a new version after a range add update. 2.1. Choose the old version from which the update starts. 2.2. Start from the root of that old version. 2.3. Move only through segments that intersect the update range. 2.4. Before changing any visited node, create a copy of that node. 2.5. If the copied segment is fully inside the update range, add the update to this copied node and stop going deeper. 2.6. If the copied segment is only partly inside the update range, continue only into the necessary children. 2.7. After the children are processed, recompute the copied node from its children and from its own lazy value. 2.8. The copied root becomes the root of the new version. 3. Answer a range sum query in any version. 3.1. Choose the version whose array we want to inspect. 3.2. Start from the root of that version. 3.3. If a segment is completely outside the query range, it contributes nothing. 3.4. If a segment is completely inside the query range, use the sum already stored in that node. 3.5. If a segment is only partly inside the query range, ask the necessary children. 3.6. Also add the contribution of the current node's lazy value to the part of the query that lies inside this segment. 3.7. The sum of these contributions is the answer. 4. Maintain the meaning of a node. 4.1. Each node represents one fixed segment of the array. 4.2. Its sum is the total value of that segment after all updates stored on this node and below it. 4.3. Its lazy value means: every position inside this segment has this additional value from this node. 4.4. Its child links may point to old nodes, because unchanged parts are shared between versions. 5. Keep old versions safe. 5.1. Never edit a node that already belongs to an existing version. 5.2. Copy the node first, then edit only the copy. 5.3. Reuse old child links whenever the update does not need to change that child.

#include <bits/stdc++.h> using namespace std; struct Node { int L; int R; long long sum; long long lz; Node() { L = 0; R = 0; sum = 0; lz = 0; } Node(long long x) { L = 0; R = 0; sum = x; lz = 0; } }; 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; } void pull(int x, int l, int r) { if (l == r) { return; } t[x].sum = comb(t[t[x].L].sum, t[t[x].R].sum) + t[x].lz * (r - l + 1); } void apply(int x, int l, int r, long long y) { t[x].sum += y * (r - l + 1); t[x].lz += y; } 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); pull(x, l, r); return x; } int upd(int x, int l, int r, int tl, int tr, long long y) { if (tl > tr) { return x; } else if (l == tl && r == tr) { int cur = clone(x); apply(cur, l, r, y); return cur; } int cur = clone(x); int m = (l + r) / 2; t[cur].L = upd(t[cur].L, l, m, tl, min(m, tr), y); t[cur].R = upd(t[cur].R, m + 1, r, max(m + 1, tl), tr, y); pull(cur, l, r); return cur; } long long get(int x, int l, int r, int tl, int tr) { if (tl > tr) { return 0; } else if (l == tl && r == tr) { return t[x].sum; } int m = (l + r) / 2; long long res = 0; res += get(t[x].L, l, m, tl, min(m, tr)); res += get(t[x].R, m + 1, r, max(m + 1, tl), tr); res += t[x].lz * (tr - tl + 1); return res; } 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) * 70); 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 1

Introduction

Problem or motivation

Alternative approach

Core concept

Main algorithm

Implementation

Complexity