diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/datastructures.tex | 8 | ||||
| -rw-r--r-- | datastructures/treap2.cpp | 3 |
2 files changed, 6 insertions, 5 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index fc72b0b..85ad693 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -89,6 +89,10 @@ \sourcecode{datastructures/stlTree.cpp} \end{algorithm} +\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} + \sourcecode{datastructures/stlRope.cpp} +\end{algorithm} + \begin{algorithm}{STL HashMap} 3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map} \sourcecode{datastructures/stlHashMap.cpp} @@ -99,10 +103,6 @@ \sourcecode{datastructures/stlPQ.cpp} \end{algorithm} -\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} - \sourcecode{datastructures/stlRope.cpp} -\end{algorithm} - \begin{algorithm}{Lower/Upper Envelope (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. \sourcecode{datastructures/monotonicConvexHull.cpp} diff --git a/datastructures/treap2.cpp b/datastructures/treap2.cpp index 5d0aefa..10168ca 100644 --- a/datastructures/treap2.cpp +++ b/datastructures/treap2.cpp @@ -41,7 +41,8 @@ struct Treap { upd(v); return {left, v}; } else { - auto [left, right] = split(V->r, k - getSize(V->l) - 1); // and only "k" + // and only "k" + auto [left, right] = split(V->r, k - getSize(V->l) - 1); V->r = left; upd(v); return {v, right}; |