From 7437e9268925c6550704ea2dde9d6a5f7137f4cc Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Sun, 17 Nov 2024 02:02:28 +0100
Subject: generalise segment tree binary search

---
 content/datastructures/datastructures.tex  |  2 +-
 content/datastructures/lazyPropagation.cpp | 14 ++++++++------
 2 files changed, 9 insertions(+), 7 deletions(-)

(limited to 'content/datastructures')

diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index 4bbe507..0495543 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -10,7 +10,7 @@
 	
 	\subsubsection{Lazy Propagation}
 	Assignment modifications, sum queries \\
-	\method{lower\_bound}{erster Index in $[l, r)$ $\geq x$ (erfordert max-combine)}{\log(n)}
+	\method{binary\_search}{kleinstes $x$ in $[l, r]$ mit $f(\text{query}(l, x))$ (monoton in $x$)}{\log(n)}
 	\sourcecode{datastructures/lazyPropagation.cpp}
 \end{algorithm}
 
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp
index 82176cb..a5be822 100644
--- a/content/datastructures/lazyPropagation.cpp
+++ b/content/datastructures/lazyPropagation.cpp
@@ -63,21 +63,23 @@ struct SegTree {
 	}
 
 	// Optional:
-	int lower_bound(int l, int r, T x) {
+	int binary_search(int l, int r, auto &&f) {
+		if (f(E)) return l;
 		l += n, r += n;
-		push(l), push(r - 1);
+		push(l), push(r);
 		int a[64] = {}, lp = 0, rp = 64;
 		for (; l < r; l /= 2, r /= 2) {
 			if (l&1) a[lp++] = l++;
 			if (r&1) a[--rp] = --r;
 		}
-		for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this
+		T x = E, y = x;
+		for (int i : a) if (i != 0 && f(x = comb(y = x, tree[i]))) {
 			while (i < n) {
 				push_down(i);
-				if (tree[2 * i] >= x) i = 2 * i; // And this
-				else i = 2 * i + 1;
+				if (f(x = comb(y, tree[2*i]))) i = 2 * i;
+				else i = 2 * i + 1, y = x;
 			}
-			return i - n;
+			return i - n + 1;
 		}
 		return -1;
 	}
-- 
cgit v1.2.3