Improved Lazy Segment Tree

5 files changed, 106 insertions, 124 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 9e954e7..fc72b0b 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -19,12 +19,11 @@
 	\sourcecode{datastructures/segmentTree.cpp}
 	
 	\subsubsection{Lazy Propagation}
-	Increment modifications, maximum queries
-	\sourcecode{datastructures/lazyPropagation1.cpp}
-	
-	Assignment modifications, sum queries
-	\sourcecode{datastructures/lazyPropagation2.cpp}
+	Assignment modifications, sum queries \\
+		\method{find\_first}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)}
+	\sourcecode{datastructures/lazyPropagation.cpp}
 \end{algorithm}
+\clearpage
 
 \begin{algorithm}{Fenwick Tree}
 	\begin{methods}
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp
new file mode 100644
index 0000000..4817b16
--- /dev/null
+++ b/datastructures/lazyPropagation.cpp
@@ -0,0 +1,85 @@
+struct SegTree {
+	int size, height;
+	static constexpr ll neutral = 0; // Neutral element for combine
+	static constexpr ll updateFlag = 0; // Unused value by updates
+	vector<ll> tree, lazy;
+
+	SegTree(const vector<ll>& a) : SegTree(sz(a)) {
+		copy(all(a), tree.begin() + size);
+		for (int i = size - 1; i > 0; i--)
+			tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
+	}
+
+	SegTree(int n) : size(n), height(__lg(2 * n)),
+		tree(2 * n, neutral), lazy(n, updateFlag) {}
+
+	ll combine(ll a, ll b) {return a + b;} // Modify this + neutral
+
+	void apply(int i, ll val, int k) { // And this + updateFlag
+		tree[i] = val * k;
+		if (i < size) lazy[i] = val; // Don't forget this
+	}
+
+	void push_down(int i, int k) {
+		if (lazy[i] != updateFlag) {
+			apply(2 * i, lazy[i], k);
+			apply(2 * i + 1, lazy[i], k);
+			lazy[i] = updateFlag;
+	}}
+
+	void push(int i) {
+		for (int s = height, k = 1 << (height-1); s > 0; s--, k /= 2)
+			push_down(i >> s, k);
+	}
+
+	void build(int i) {
+		for (int k = 2; i /= 2; k *= 2) {
+			push_down(i, k / 2);
+			tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
+	}}
+
+	void update(int l, int r, ll val) { // data[l..r) = val
+		l += size, r += size;
+		int l0 = l, r0 = r;
+		push(l0), push(r0 - 1);
+		for (int k = 1; l < r; l /= 2, r /= 2, k *= 2) {
+			if (l&1) apply(l++, val, k);
+			if (r&1) apply(--r, val, k);
+		}
+		build(l0), build(r0 - 1);
+	}
+
+	ll query(int l, int r) { // sum[l..r)
+		l += size, r += size;
+		push(l), push(r - 1);
+		ll resL = neutral, resR = neutral;
+		for (; l < r; l /= 2, r /= 2) {
+			if (l&1) resL = combine(resL, tree[l++]);
+			if (r&1) resR = combine(tree[--r], resR);
+		}
+		return combine(resL, resR);
+	}
+
+	// Optional:
+	ll find_first(int l, int r, int x) {
+		l += size, r += size;
+		push(l), push(r - 1);
+		vector<pair<int, int>> a; stack<pair<int, int>> st;
+		for (int k = 1; l < r; l /= 2, r /= 2, k *= 2) {
+			if (l&1) a.emplace_back(l++, k);
+			if (r&1) st.emplace(--r, k);
+		}
+		while (!st.empty()) a.push_back(st.top()), st.pop();
+		for (auto [i, k] : a) {
+			if (tree[i] >= x) return find(i, x, k); // Modify this
+		}
+		return -1;
+	}
+
+	ll find(int i, int x, int k) {
+		if (i >= size) return i - size;
+		push_down(i, k / 2);
+		if (tree[2*i] >= x) return find(2 * i, x, k / 2); // And this
+		else return find(2 * i + 1, x, k / 2);
+	}
+};
diff --git a/datastructures/lazyPropagation1.cpp b/datastructures/lazyPropagation1.cpp
deleted file mode 100644
index c1ffcf0..0000000
--- a/datastructures/lazyPropagation1.cpp
+++ /dev/null
@@ -1,49 +0,0 @@
-int h; // = __lg(2*n)
-//a neutral value for the update:
-constexpr ll updateFlag = 0;
-vector<ll> d(N, updateFlag);
-
-void apply(int p, ll value) {
-	tree[p] += value;
-	if (p < sz(tree)/2) d[p] += value;
-}
-
-void build(int p) {
-	p >>= __builtin_ctzll(p);
-	while (p > 1) {
-		p/=2;
-		tree[p] = max(tree[2*p], tree[2*p+1]) + d[p];
-}}
-
-void push(int p) {
-	for (int s = h; s > 0; s--) {
-		int i = p >> s;
-		if (d[i] != updateFlag) {
-			apply(2*i  , d[i]);
-			apply(2*i+1, d[i]);
-			d[i] = updateFlag;
-}}}
-
-void update(int l, int r, ll value) { // data[l..r)+=value
-	l += sz(tree)/2, r += sz(tree)/2;
-	int l0 = l, r0 = r;
-	for (; l < r; l /= 2, r /= 2) {
-		if (l&1) apply(l++, value);
-		if (r&1) apply(--r, value);
-	}
-	build(l0);
-	build(r0 - 1);
-}
-
-ll query(int l, int r) { // max[l..r)
-	l += sz(tree)/2, r += sz(tree)/2;
-	push(l);
-	push(r - 1);
-	ll res = query_default;
-	for (; l < r; l /= 2, r /= 2) {
-		if (l&1) res = max(res, tree[l++]);
-		if (r&1) res = max(tree[--r], res);
-	}
-	return res;
-}
-
diff --git a/datastructures/lazyPropagation2.cpp b/datastructures/lazyPropagation2.cpp
deleted file mode 100644
index b44b362..0000000
--- a/datastructures/lazyPropagation2.cpp
+++ /dev/null
@@ -1,52 +0,0 @@
-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 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 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 update(int l, int r, ll value) { // data[l..r)=value
-	if (value == updateFlag) return;
-	l += sz(tree)/2, r += sz(tree)/2;
-	push(l);
-	push(r - 1);
-	int l0 = l, r0 = r, k = 1;
-	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);
-	build(r0 - 1);
-}
-
-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 < r; l /= 2, r /= 2) {
-		if (l&1) res = res + tree[l++];
-		if (r&1) res = tree[--r] + res;
-	}
-	return res;
-}
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp
index eb59d00..7b97f57 100644
--- a/datastructures/segmentTree.cpp
+++ b/datastructures/segmentTree.cpp
@@ -1,25 +1,24 @@
 vector<ll> tree;
-constexpr ll query_default = 0;
+constexpr ll neutral = 0; // Neutral element for combine
 
 ll combine(ll a, ll b) {
 	return a + b;
 }
 
-void init(vector<ll>& values) {
-	tree.assign(sz(values)*2, 0);
-	copy(all(values), tree.begin() + sz(values));
-	for (int i = sz(tree)/2 - 1; i > 0; --i) {
-		tree[i] = combine(tree[2*i], tree[2*i+1]);
+void init(vector<ll>& a) {
+	tree.assign(2 * sz(a), 0);
+	copy(all(a), tree.begin() + sz(a));
+	for (int i = sz(tree)/2 - 1; i > 0; i--) {
+		tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
 }}
 
-void update(int p, ll value) {
-	for (tree[p += sz(tree)/2] = value, p /= 2; p > 0; p /= 2) {
-		tree[p] = combine(tree[2*p], tree[2*p+1]);
+void update(int i, ll val) {
+	for (tree[i += sz(tree)/2] = val; i /= 2; ) {
+		tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
 }}
 
 ll query(int l, int r) {
-	ll resL = query_default;
-	ll resR = query_default;
+	ll resL = neutral, resR = neutral;
 	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) {
 		if (l&1) resL = combine(resL, tree[l++]);
 		if (r&1) resR = combine(tree[--r], resR);
@@ -28,16 +27,16 @@ ll query(int l, int r) {
 }
 
 // Oder: Intervall-Modifikation, Punkt-Query:
-void modify(int l, int r, ll value) {
+void modify(int l, int r, ll val) {
 	for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) {
-		if (l&1) {tree[l] = combine(tree[l], value); l++;};
-		if (r&1) {--r; tree[r] = combine(value, tree[r]);};
+		if (l&1) {tree[l] = combine(tree[l], val); l++;};
+		if (r&1) {--r; tree[r] = combine(tree[r], val);};
 }}
 
-ll query(int p) {
-	ll res = query_default;
-	for (p += sz(tree)/2; p > 0; p = p/2) {
-		res = combine(res, tree[p]);
+ll query(int i) {
+	ll res = neutral;
+	for (i += sz(tree)/2; i > 0; i /= 2) {
+		res = combine(res, tree[i]);
 	}
 	return res;
 }