Improved Lazy Segment Tree

1 files changed, 0 insertions, 49 deletions

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;
-}
-