Adding dynamic variant of convex hull optimization.

3 files changed, 61 insertions, 0 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index b3683bf..a31edef 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -27,3 +27,8 @@
 
 \subsection{Skew Heap}
 \lstinputlisting{datastructures/skewHeap.cpp}
+
+\subsection{Lower/Upper Envelop (Convex Hull Optimization)}
+Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
+\lstinputlisting{datastructures/monotonicConvexHull.cpp}
+\lstinputlisting{datastructures/dynamicConvexHull.cpp}
diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..9ccf220
--- /dev/null
+++ b/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,35 @@
+// Upper Envelope, dynamisch.
+struct Line {
+    ll m, b;
+    mutable function<const Line*()> succ;
+    bool operator<(const Line& rhs) const {
+        if (rhs.b != is_query) return m < rhs.m;
+        const Line* s = succ();
+        if (!s) return 0;
+        ll x = rhs.m;
+        return b - s->b < (s->m - m) * x;
+    }
+};
+struct HullDynamic : public multiset<Line> {
+    bool bad(iterator y) {
+        auto z = next(y);
+        if (y == begin()) {
+            if (z == end()) return 0;
+            return y->m == z->m && y->b <= z->b;
+        }
+        auto x = prev(y);
+        if (z == end()) return y->m == x->m && y->b <= x->b;
+        return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
+    }
+    void insert_line(ll m, ll b) { // Laufzeit: O(log(n))
+        auto y = insert({ m, b });
+        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
+        if (bad(y)) { erase(y); return; }
+        while (next(y) != end() && bad(next(y))) erase(next(y));
+        while (y != begin() && bad(prev(y))) erase(prev(y));
+    }
+    ll query(ll x) { // Laufzeit: O(log(n))
+        auto l = *lower_bound((Line) { x, -(1LL<<62) });
+        return l.m * x + l.b;
+    }
+};
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
new file mode 100644
index 0000000..a93bfae
--- /dev/null
+++ b/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,21 @@
+// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
+// Gerade hat kleinere Steigung als alle vorherigen.
+vector<ll> ms, bs; int ptr = 0;
+
+bool bad(int l1, int l2, int l3) {
+  return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < (bs[l2]-bs[l1])*(ms[l1]-ms[l3]);
+}
+
+void add(ll m, ll b) { // Laufzeit O(1) amortisiert
+  ms.push_back(m); bs.push_back(b);
+  while (ms.size() >= 3 && bad(ms.size() - 3, ms.size() - 2, ms.size() - 1)) {
+    ms.erase(ms.end() - 2); bs.erase(bs.end() - 2);
+}}
+
+ll get(int idx, ll x) { return ms[idx] * x + bs[idx]; }
+
+ll query(ll x) { // Laufzeit: O(1) amortisiert
+  if (ptr >= (int)ms.size()) ptr = ms.size() - 1;
+  while (ptr < (int)ms.size() - 1 && get(ptr + 1, x) < get(ptr, x)) ptr++;
+  return ms[ptr] * x + bs[ptr];
+}