From da3552d151fff109f85316ce6eaa3b503662078a Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Thu, 16 Feb 2023 15:00:13 +0100
Subject: unified lazy propagation examples

---
 datastructures/lazyPropagation2.cpp | 62 +++++++++++++++++++------------------
 1 file changed, 32 insertions(+), 30 deletions(-)

(limited to 'datastructures/lazyPropagation2.cpp')

diff --git a/datastructures/lazyPropagation2.cpp b/datastructures/lazyPropagation2.cpp
index e90c671..6529102 100644
--- a/datastructures/lazyPropagation2.cpp
+++ b/datastructures/lazyPropagation2.cpp
@@ -1,50 +1,52 @@
-void calc(int p, ll k) {
-	if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1];
-	else tree[p] = d[p] * k;
-}
+int h; // = __lg(2*n)
+//a value that is not used by the update query:
+constexpr ll updateFlag = -1;
+vector<ll> d(N, updateFlag);
 
 void apply(int p, ll value, int k) {
 	tree[p] = value * k;
 	if (p < sz(tree)/2) d[p] = value;
 }
 
-void build(int l, int r) {
-	int k = 2;
-	for (l += sz(tree)/2, r += sz(tree)/2-1; l > 1; k <<= 1) {
-		l/=2, r/=2;
-		for (int i = r; i >= l; --i) calc(i, k);
+void build(int p) {
+	p >>= __builtin_ctzll(p);
+	for (int k = 2; p > 1; k <<= 1) {
+		p/=2;
+		if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1];
+		else tree[p] = d[p] * k;
 }}
 
-void push(int l, int r) {
-	int s = h, k = 1 << (h-1);
-	for (l += sz(tree)/2, r += sz(tree)/2-1; s > 0; --s, k/=2) {
-		for (int i = l >> s; i <= r >> s; ++i) {
-			if (d[i] != updateFlag) {
-				apply(2*i  , d[i], k);
-				apply(2*i+1, d[i], k);
-				d[i] = updateFlag;
-}}}}
+void push(int p) {
+	for (int s = h, k = 1 << (h-1); s > 0; s--, k/=2) {
+		int i = p >> s;
+		if (d[i] != updateFlag) {
+			apply(2*i  , d[i], k);
+			apply(2*i+1, d[i], k);
+			d[i] = updateFlag;
+}}}
 
-void modify(int l, int r, ll value) {
+void update(int l, int r, ll value) { // assign value
 	if (value == updateFlag) return;
-	push(l, l + 1);
-	push(r - 1, r);
+	l += sz(tree)/2, r += sz(tree)/2;
+	push(l);
+	push(r - 1);
 	int l0 = l, r0 = r, k = 1;
-	for (l += sz(tree)/2, r += sz(tree)/2; l<r; l/=2, r/=2, k*=2) {
+	for (; l < r; l /= 2, r /= 2, k *= 2) {
 		if (l&1) apply(l++, value, k);
 		if (r&1) apply(--r, value, k);
 	}
-	build(l0, l0 + 1);
-	build(r0 - 1, r0);
+	build(l0);
+	build(r0 - 1);
 }
 
-ll query(int l, int r) {
-	push(l, l + 1);
-	push(r - 1, r);
+ll query(int l, int r) { // sum(l..r)
+	l += sz(tree)/2, r += sz(tree)/2;
+	push(l);
+	push(r - 1);
 	ll res = query_default;
-	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l/=2, r/=2) {
-		if (l&1) res += tree[l++];
-		if (r&1) res += tree[--r];
+	for (; l < r; l /= 2, r /= 2) {
+		if (l&1) res = res + tree[l++];
+		if (r&1) res = tree[--r] + res;
 	}
 	return res;
 }
-- 
cgit v1.2.3