diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/RMQ.cpp | 27 | ||||
| -rw-r--r-- | datastructures/datastructures.tex | 14 | ||||
| -rw-r--r-- | datastructures/fenwickTree.cpp | 2 | ||||
| -rw-r--r-- | datastructures/fenwickTree2.cpp | 2 | ||||
| -rw-r--r-- | datastructures/test/fenwickTree.cpp | 26 | ||||
| -rw-r--r-- | datastructures/test/fenwickTree2.cpp | 28 |
6 files changed, 58 insertions, 41 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp deleted file mode 100644 index 401cca4..0000000 --- a/datastructures/RMQ.cpp +++ /dev/null @@ -1,27 +0,0 @@ -vector<int> values; -vector<vector<int>> rmq; - -int select(int a, int b) { - return values[a] <= values[b] ? a : b; -} - -void build() { - for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) { - for(int l = 0; l + s <= sz(values); l++) { - if(i == 0) rmq[0][l] = l; - else { - int r = l + ss; - rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]); -}}}} - -void init(const vector<int>& v) { - values = v; - rmq = vector<vector<int>>(__lg(sz(values))+1, vector<int>(sz(values))); - build(); -} - -int query(int l, int r) { - if(l >= r) return l; - int s = __lg(r-l); r = r - (1 << s); - return select(rmq[s][l],rmq[s][r]); -} diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4139219..37a1dc2 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -17,14 +17,14 @@ \begin{algorithm}{Fenwick Tree} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von [0, i]}{\log(n)} + \method{prefix\_sum}{summe von [0, i)}{\log(n)} \method{update}{addiert ein Delta zu einem Element}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree.cpp} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von [0, i]}{\log(n)} + \method{prefix\_sum}{summe von [0, i)}{\log(n)} \method{update}{addiert ein Delta zu allen Elementen [l, r)}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} @@ -122,16 +122,6 @@ \sourcecode{datastructures/stlHashMap.cpp} \end{algorithm} - - -\begin{algorithm}[optional]{Range Minimum Query} - \begin{methods} - \method{init}{baut Struktur auf}{n\*\log(n)} - \method{query}{Index des Minimums in [l, r)}{1} - \end{methods} - \sourcecode{datastructures/RMQ.cpp} -\end{algorithm} - \begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl} \begin{methods} \method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)} diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index cac3cf8..6c5ed91 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -10,6 +10,6 @@ void init(int n) { ll prefix_sum(int i) { ll sum = 0; - for (i++; i > 0; i -= (i & (-i))) sum += tree[i]; + for (; i > 0; i -= (i & (-i))) sum += tree[i]; return sum; } diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp index ff87e2e..43c3a32 100644 --- a/datastructures/fenwickTree2.cpp +++ b/datastructures/fenwickTree2.cpp @@ -14,7 +14,7 @@ void init(vector<ll>& v) { } ll prefix_sum (int i) { - ll res = 0; i++; + ll res = 0; for (int ti = i; ti > 0; ti -= ti&(-ti)) res += add[ti] * i + mul[ti]; return res; diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp new file mode 100644 index 0000000..f9dd619 --- /dev/null +++ b/datastructures/test/fenwickTree.cpp @@ -0,0 +1,26 @@ +#include "../fenwickTree.cpp" + +void test(int n) { + vector<ll> naive(n); + init(n); + + for (int i = 0; i < 1000; i++) { + int p = util::randint(n); + ll delta = util::randint(); + update(p, delta); + naive[p] += delta; + + int r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp new file mode 100644 index 0000000..18ebcb7 --- /dev/null +++ b/datastructures/test/fenwickTree2.cpp @@ -0,0 +1,28 @@ +#include "../fenwickTree2.cpp" + +void test(int n) { + vector<ll> naive(n); + for (int i = 0; i < n; i++) naive[i] = util::randint(); + init(naive); + + for (int i = 0; i < 1000; i++) { + int l = util::randint(n), r = util::randint(n); + if (l > r) swap(l, r); + ll delta = util::randint(); + update(l, r, delta); + for (int i = l; i < r; i++) naive[i] += delta; + + r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} |