From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- datastructures/segmentTree.cpp | 58 +++++++++++++++++++++++++++--------------- 1 file changed, 37 insertions(+), 21 deletions(-) (limited to 'datastructures/segmentTree.cpp') diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 3905151..09ff694 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -1,27 +1,43 @@ -// Laufzeit: init: O(n), query: O(log n), update: O(log n) -// Berechnet das Maximum im Array. -int a[MAX_N], m[4 * MAX_N]; +vector tree; +constexpr ll query_default = 0; -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 -INF; // 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)); +ll combine(ll a, ll b) { + return a + b; } -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] = v; a[i] = v; 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(vector& values) { + tree.assign(sz(values)*2, 0); + copy(values.begin(), values.end(), tree.begin() + sz(values)); + for (int i = sz(tree)/2 - 1; i > 0; --i) { + tree[i] = combine(tree[2*i], tree[2*i+1]); +}} + +void update(int p, ll value) { + for (tree[p += sz(tree)/2] = value, p /= 2; p > 0; p /= 2) { + tree[p] = combine(tree[2*p], tree[2*p+1]); +}} + +ll query(int l, int r) { + ll resL = query_default; + ll resR = query_default; + for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) { + if (l&1) resL = combine(resL, tree[l++]); + if (r&1) resR = combine(tree[--r], resR); + } + return combine(resL, resR); } -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]); +// Oder: Intervall-Modifikation, Punkt-Query: +void modify(int l, int r, ll value) { + for (l += sz(tree)/2, r += sz(tree)/2; l < r; l /= 2, r /= 2) { + if (l&1) {tree[l] = combine(tree[l], value); l++;}; + if (r&1) {--r; tree[r] = combine(value, tree[r]);}; +}} + +ll query(int p) { + ll res = query_default; + for (p += sz(tree)/2; p > 0; p = p/2) { + res = combine(res, tree[p]); + } + return res; } -- cgit v1.2.3