From b40b4fbc8222226608c64013e56226044884374e Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 23 Feb 2023 14:57:25 +0100 Subject: changed names --- datastructures/datastructures.tex | 2 +- datastructures/lazyPropagation.cpp | 8 ++++---- tcr.pdf | Bin 648767 -> 648707 bytes 3 files changed, 5 insertions(+), 5 deletions(-) diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 578eaba..dac8656 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -20,7 +20,7 @@ \subsubsection{Lazy Propagation} Assignment modifications, sum queries \\ - \method{find\_first}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)} + \method{lower\_bound}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)} \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 4817b16..ed5438f 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -61,15 +61,15 @@ struct SegTree { } // Optional: - ll find_first(int l, int r, int x) { + ll lower_bound(int l, int r, int x) { l += size, r += size; push(l), push(r - 1); - vector> a; stack> st; + vector> a, 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); + if (r&1) st.emplace_back(--r, k); } - while (!st.empty()) a.push_back(st.top()), st.pop(); + a.insert(a.begin(), st.rbegin(), st.rend()); for (auto [i, k] : a) { if (tree[i] >= x) return find(i, x, k); // Modify this } diff --git a/tcr.pdf b/tcr.pdf index 8d70ee6..e4c7464 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3