From ac16d3eb6c2d9058495a2f88a747e7d24ce3a095 Mon Sep 17 00:00:00 2001 From: pjungeblut Date: Sun, 2 Nov 2014 16:57:06 +0100 Subject: union find und Segementbaum --- datastructures/segmentTree.cpp | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 datastructures/segmentTree.cpp (limited to 'datastructures/segmentTree.cpp') diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp new file mode 100644 index 0000000..6b73ec0 --- /dev/null +++ b/datastructures/segmentTree.cpp @@ -0,0 +1,32 @@ +int a[MAX_N], m[4 * MAX_N]; + +int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) { + if (x <= X && Y <= y) return m[k]; + if (y < X || Y < x) return -1000000000; //ein "neutrales" Element + int M = (X + Y) / 2; + return max(query(x, y, 2 * k + 1, X, M), query(x, y, 2 * k + 2, M + 1, Y)); +} + +void update(int i, int v, int k = 0, int X = 0, int Y = MAX_N - 1) { + if (i < X || Y < i) return; + if (X == Y) { + m[k] = w; + a[i] = w; + return; + } + int M = (X + Y) / 2; + update(i, v, 2 * k + 1, X, M); + update(i, v, 2 * k + 2, M + 1, Y); + m[k] = max(m[2 * k + 1], m[2 * k + 2]); +} + +void init(int k = 0, int X = 0, int Y = MAX_N - 1) { + if (X == Y) { + m[k] = a[X]; + return; + } + int M = (X + Y) / 2; + init(2 * k + 1, X, M); + init(2 * k + 2, M + 1, Y); + m[k] = max(m[2 * k + 1], m[2 * k + 2]); +} \ No newline at end of file -- cgit v1.2.3