summaryrefslogtreecommitdiff
path: root/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures')
-rw-r--r--datastructures/datastructures.tex9
-rw-r--r--datastructures/lazyPropagation.cpp85
-rw-r--r--datastructures/lazyPropagation1.cpp49
-rw-r--r--datastructures/lazyPropagation2.cpp52
-rw-r--r--datastructures/segmentTree.cpp35
5 files changed, 106 insertions, 124 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 9e954e7..fc72b0b 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -19,12 +19,11 @@
\sourcecode{datastructures/segmentTree.cpp}
\subsubsection{Lazy Propagation}
- Increment modifications, maximum queries
- \sourcecode{datastructures/lazyPropagation1.cpp}
-
- Assignment modifications, sum queries
- \sourcecode{datastructures/lazyPropagation2.cpp}
+ Assignment modifications, sum queries \\
+ \method{find\_first}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)}
+ \sourcecode{datastructures/lazyPropagation.cpp}
\end{algorithm}
+\clearpage
\begin{algorithm}{Fenwick Tree}
\begin{methods}
diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp
new file mode 100644
index 0000000..4817b16
--- /dev/null
+++ b/datastructures/lazyPropagation.cpp
@@ -0,0 +1,85 @@
+struct SegTree {
+ int size, height;
+ static constexpr ll neutral = 0; // Neutral element for combine
+ static constexpr ll updateFlag = 0; // Unused value by updates
+ vector<ll> tree, lazy;
+
+ SegTree(const vector<ll>& a) : SegTree(sz(a)) {
+ copy(all(a), tree.begin() + size);
+ for (int i = size - 1; i > 0; i--)
+ tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
+ }
+
+ SegTree(int n) : size(n), height(__lg(2 * n)),
+ tree(2 * n, neutral), lazy(n, updateFlag) {}
+
+ ll combine(ll a, ll b) {return a + b;} // Modify this + neutral
+
+ void apply(int i, ll val, int k) { // And this + updateFlag
+ tree[i] = val * k;
+ if (i < size) lazy[i] = val; // Don't forget this
+ }
+
+ void push_down(int i, int k) {
+ if (lazy[i] != updateFlag) {
+ apply(2 * i, lazy[i], k);
+ apply(2 * i + 1, lazy[i], k);
+ lazy[i] = updateFlag;
+ }}
+
+ void push(int i) {
+ for (int s = height, k = 1 << (height-1); s > 0; s--, k /= 2)
+ push_down(i >> s, k);
+ }
+
+ void build(int i) {
+ for (int k = 2; i /= 2; k *= 2) {
+ push_down(i, k / 2);
+ tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
+ }}
+
+ void update(int l, int r, ll val) { // data[l..r) = val
+ l += size, r += size;
+ int l0 = l, r0 = r;
+ push(l0), push(r0 - 1);
+ for (int k = 1; l < r; l /= 2, r /= 2, k *= 2) {
+ if (l&1) apply(l++, val, k);
+ if (r&1) apply(--r, val, k);
+ }
+ build(l0), build(r0 - 1);
+ }
+
+ ll query(int l, int r) { // sum[l..r)
+ l += size, r += size;
+ push(l), push(r - 1);
+ ll resL = neutral, resR = neutral;
+ for (; 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);
+ }
+
+ // Optional:
+ ll find_first(int l, int r, int x) {
+ l += size, r += size;
+ push(l), push(r - 1);
+ vector<pair<int, int>> a; stack<pair<int, int>> 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);
+ }
+ while (!st.empty()) a.push_back(st.top()), st.pop();
+ for (auto [i, k] : a) {
+ if (tree[i] >= x) return find(i, x, k); // Modify this
+ }
+ return -1;
+ }
+
+ ll find(int i, int x, int k) {
+ if (i >= size) return i - size;
+ push_down(i, k / 2);
+ if (tree[2*i] >= x) return find(2 * i, x, k / 2); // And this
+ else return find(2 * i + 1, x, k / 2);
+ }
+};
diff --git a/datastructures/lazyPropagation1.cpp b/datastructures/lazyPropagation1.cpp
deleted file mode 100644
index c1ffcf0..0000000
--- a/datastructures/lazyPropagation1.cpp
+++ /dev/null
@@ -1,49 +0,0 @@
-int h; // = __lg(2*n)
-//a neutral value for the update:
-constexpr ll updateFlag = 0;
-vector<ll> d(N, updateFlag);
-
-void apply(int p, ll value) {
- tree[p] += value;
- if (p < sz(tree)/2) d[p] += value;
-}
-
-void build(int p) {
- p >>= __builtin_ctzll(p);
- while (p > 1) {
- p/=2;
- tree[p] = max(tree[2*p], tree[2*p+1]) + d[p];
-}}
-
-void push(int p) {
- for (int s = h; s > 0; s--) {
- int i = p >> s;
- if (d[i] != updateFlag) {
- apply(2*i , d[i]);
- apply(2*i+1, d[i]);
- d[i] = updateFlag;
-}}}
-
-void update(int l, int r, ll value) { // data[l..r)+=value
- l += sz(tree)/2, r += sz(tree)/2;
- int l0 = l, r0 = r;
- for (; l < r; l /= 2, r /= 2) {
- if (l&1) apply(l++, value);
- if (r&1) apply(--r, value);
- }
- build(l0);
- build(r0 - 1);
-}
-
-ll query(int l, int r) { // max[l..r)
- l += sz(tree)/2, r += sz(tree)/2;
- push(l);
- push(r - 1);
- ll res = query_default;
- for (; l < r; l /= 2, r /= 2) {
- if (l&1) res = max(res, tree[l++]);
- if (r&1) res = max(tree[--r], res);
- }
- return res;
-}
-
diff --git a/datastructures/lazyPropagation2.cpp b/datastructures/lazyPropagation2.cpp
deleted file mode 100644
index b44b362..0000000
--- a/datastructures/lazyPropagation2.cpp
+++ /dev/null
@@ -1,52 +0,0 @@
-int h; // = __lg(2*n)
-//a value that is not used by the update query:
-constexpr ll updateFlag = -1;
-vector<ll> d(N, updateFlag);
-
-void apply(int p, ll value, int k) {
- tree[p] = value * k;
- if (p < sz(tree)/2) d[p] = value;
-}
-
-void build(int p) {
- p >>= __builtin_ctzll(p);
- for (int k = 2; p > 1; k <<= 1) {
- p/=2;
- if (d[p] == updateFlag) tree[p] = tree[2*p] + tree[2*p+1];
- else tree[p] = d[p] * k;
-}}
-
-void push(int p) {
- for (int s = h, k = 1 << (h-1); s > 0; s--, k/=2) {
- int i = p >> s;
- if (d[i] != updateFlag) {
- apply(2*i , d[i], k);
- apply(2*i+1, d[i], k);
- d[i] = updateFlag;
-}}}
-
-void update(int l, int r, ll value) { // data[l..r)=value
- if (value == updateFlag) return;
- l += sz(tree)/2, r += sz(tree)/2;
- push(l);
- push(r - 1);
- int l0 = l, r0 = r, k = 1;
- for (; l < r; l /= 2, r /= 2, k *= 2) {
- if (l&1) apply(l++, value, k);
- if (r&1) apply(--r, value, k);
- }
- build(l0);
- build(r0 - 1);
-}
-
-ll query(int l, int r) { // sum[l..r)
- l += sz(tree)/2, r += sz(tree)/2;
- push(l);
- push(r - 1);
- ll res = query_default;
- for (; l < r; l /= 2, r /= 2) {
- if (l&1) res = res + tree[l++];
- if (r&1) res = tree[--r] + res;
- }
- return res;
-}
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp
index eb59d00..7b97f57 100644
--- a/datastructures/segmentTree.cpp
+++ b/datastructures/segmentTree.cpp
@@ -1,25 +1,24 @@
vector<ll> tree;
-constexpr ll query_default = 0;
+constexpr ll neutral = 0; // Neutral element for combine
ll combine(ll a, ll b) {
return a + b;
}
-void init(vector<ll>& values) {
- tree.assign(sz(values)*2, 0);
- copy(all(values), 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 init(vector<ll>& a) {
+ tree.assign(2 * sz(a), 0);
+ copy(all(a), tree.begin() + sz(a));
+ 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]);
+void update(int i, ll val) {
+ for (tree[i += sz(tree)/2] = val; i /= 2; ) {
+ tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
}}
ll query(int l, int r) {
- ll resL = query_default;
- ll resR = query_default;
+ ll resL = neutral, resR = neutral;
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);
@@ -28,16 +27,16 @@ ll query(int l, int r) {
}
// Oder: Intervall-Modifikation, Punkt-Query:
-void modify(int l, int r, ll value) {
+void modify(int l, int r, ll val) {
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]);};
+ if (l&1) {tree[l] = combine(tree[l], val); l++;};
+ if (r&1) {--r; tree[r] = combine(tree[r], val);};
}}
-ll query(int p) {
- ll res = query_default;
- for (p += sz(tree)/2; p > 0; p = p/2) {
- res = combine(res, tree[p]);
+ll query(int i) {
+ ll res = neutral;
+ for (i += sz(tree)/2; i > 0; i /= 2) {
+ res = combine(res, tree[i]);
}
return res;
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:56:12 +0000