updating libraries

8 files changed, 152 insertions, 31 deletions

diff --git a/Data Structures/dynamic_segment_tree.cpp b/Data Structures/dynamic_segment_tree.cpp
index 3ef368b..454ec01 100644
--- a/Data Structures/dynamic_segment_tree.cpp
+++ b/Data Structures/dynamic_segment_tree.cpp
@@ -8,7 +8,7 @@ struct node {
 	node* get_c(int i) {
 		return (!c[i] ? c[i] = new node : c[i]);
 	}
-	void update(int x, long long v, int l, int r) {
+	void update(int x, int v, int l, int r) {
 		if (l == r) val += v;
 		else {
 			int m = (l + r) >> 1;
@@ -16,10 +16,10 @@ struct node {
 			val = (c[0] ? c[0]->val : 0) + (c[1] ? c[1]->val : 0);
 		}
 	}
-	long long query(int a, int b, int l, int r) {
+	int query(int a, int b, int l, int r) {
 		if (a > r || b < l) return 0;
 		if (a <= l && b >= r) return val;
 		int m = (l + r) >> 1;
 		return (c[0] ? c[0]->query(a, b, l, m) : 0) + (c[1] ? c[1]->query(a, b, m + 1, r) : 0);
 	}
-};
+};
\ No newline at end of file
diff --git a/Data Structures/dynamic_segment_tree_2d.cpp b/Data Structures/dynamic_segment_tree_2d.cpp
index c798d7e..430447d 100644
--- a/Data Structures/dynamic_segment_tree_2d.cpp
+++ b/Data Structures/dynamic_segment_tree_2d.cpp
@@ -48,4 +48,4 @@ struct x_node {
 		int m = (l + r) >> 1;
 		return max((c[0] ? c[0]->query(xl, xr, yl, yr, l, m) : 0), (c[1] ? c[1]->query(xl, xr, yl, yr, m + 1, r) : 0));
 	}
-} root;
+} root;
\ No newline at end of file
diff --git a/Data Structures/fenwick_tree.cpp b/Data Structures/fenwick_tree.cpp
index dd04aea..e36e798 100644
--- a/Data Structures/fenwick_tree.cpp
+++ b/Data Structures/fenwick_tree.cpp
@@ -1,11 +1,8 @@
-#include <vector>
-using namespace std;
-
 class fenwick_tree {
 private: vector<int> FT;
 public:
 	fenwick_tree(int N) { FT.assign(N + 1, 0); }
 	void update(int x, int val) { for (; x < FT.size(); x += x & -x) FT[x] += val; }
-	int query(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x]; return ret; }
+	int query(int x) { int ret = 0; if (x > 0) for (; x > 0; x -= x & -x) ret += FT[x]; return ret; }
 	int query(int x, int y) { return query(y) - (x == 1 ? 0 : query(x - 1)); }
-};
+};
\ No newline at end of file
diff --git a/Data Structures/fenwick_tree_2d.cpp b/Data Structures/fenwick_tree_2d.cpp
index f40c7e3..64d1a78 100644
--- a/Data Structures/fenwick_tree_2d.cpp
+++ b/Data Structures/fenwick_tree_2d.cpp
@@ -1,6 +1,3 @@
-#include <vector>
-using namespace std;
-
 class fenwick_tree_2d {
 private: int N, M; vector<vector<int>> FT;
 public:
@@ -10,18 +7,18 @@ public:
 		for (int i = 0; i < N; i++) FT[i].resize(M, 0);
 	}
 	void update(int x, int y, int val) {
-		for (; x < N; x += x & -x) {
-			for (; y < M; y += y & -y) FT[x][y] += val;
+		for (int i = x; i < N; i += i & -i) {
+			for (int j = y; j < M; j += j & -j) FT[i][j] += val;
 		}
 	}
 	int query(int x, int y) {
 		int ret = 0;
-		for (; x > 0; x -= x & -x) {
-			for (; y > 0; y -= y & -y) ret += FT[x][y];
+		for (int i = x; i > 0; i -= i & -i) {
+			for (int j = y; j > 0; j -= j & -j) ret += FT[i][j];
 		}
 		return ret;
 	}
 	int query(int xl, int xr, int yl, int yr) {
 		return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) + query(xl - 1, yl - 1);
 	}
-};
+};
\ No newline at end of file
diff --git a/Data Structures/optimized_segment_tree.cpp b/Data Structures/optimized_segment_tree.cpp
new file mode 100644
index 0000000..99bf8ff
--- /dev/null
+++ b/Data Structures/optimized_segment_tree.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+using namespace std;
+
+const int N = 1e5;  // limit for array size
+int n;  // array size
+int t[2 * N];
+
+void build() {  // build the tree
+	for (int i = n - 1; i > 0; --i) t[i] = t[i << 1] + t[i << 1 | 1];
+}
+
+void modify(int p, int value) {  // set value at position p
+	for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
+}
+
+int query(int l, int r) {  // sum on interval [l, r)
+	int res = 0;
+	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
+		if (l & 1) res += t[l++];
+		if (r & 1) res += t[--r];
+	}
+	return res;
+}
+
+int main() {
+	cin >> n;
+	for (int i = 0; i < n; ++i) cin >> t[i];
+	build();
+	modify(0, 1);
+	cout << query(3, 11) << endl;
+	return 0;
+}
\ No newline at end of file
diff --git a/Data Structures/seg_fenwick_tree.cpp b/Data Structures/seg_fenwick_tree.cpp
new file mode 100644
index 0000000..a26c3de
--- /dev/null
+++ b/Data Structures/seg_fenwick_tree.cpp
@@ -0,0 +1,29 @@
+struct node {
+	int val;
+	node* c[2];
+	node() {
+		val = 0;
+		c[0] = c[1] = 0;
+	}
+	node* get_c(int i) { return (!c[i] ? c[i] = new node : c[i]); }
+	void update(int x, int v, int l = 0, int r = -1) {
+		if (r == -1) r = N - 1;
+		if (l == r) val += v;
+		else {
+			int m = (l + r) >> 1;
+			x <= m ? get_c(0)->update(x, v, l, m) : get_c(1)->update(x, v, m + 1, r);
+			val = (c[0] ? c[0]->val : 0) + (c[1] ? c[1]->val : 0);
+		}
+	}
+	long long query(int a, int b, int l = 0, int r = -1) {
+		if (r == -1) r = N - 1;
+		if (a > r || b < l) return 0;
+		if (a <= l && b >= r) return val;
+		int m = (l + r) >> 1;
+		return (c[0] ? c[0]->query(a, b, l, m) : 0) + (c[1] ? c[1]->query(a, b, m + 1, r) : 0);
+	}
+} FT[100005];
+
+void update(int x, int y, int v) { for (; x < N; x += x & -x) FT[x].update(y, v); }
+int query(int x, int y1, int y2) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x].query(y1, y2); return ret; }
+int query(int x1, int x2, int y1, int y2) { return query(x2, y1, y2) - (x1 == 1 ? 0 : query(x1 - 1, y1, y2)); }
\ No newline at end of file
diff --git a/Data Structures/segment_tree_v2.cpp b/Data Structures/segment_tree_v2.cpp
new file mode 100644
index 0000000..7057680
--- /dev/null
+++ b/Data Structures/segment_tree_v2.cpp
@@ -0,0 +1,76 @@
+template< typename T > class seg_tree {
+private:
+	int N;
+	vector<T> seg, tmp;
+public:
+	seg_tree(int size) {
+		N = size;
+		seg.resize(4 * N, 0);
+	}
+	seg_tree(int size, T A[]) {
+		N = size;
+		seg.resize(4 * N);
+		build(A);
+	}
+	seg_tree(vector<T>& A) {
+		N = A.size();
+		seg.resize(4 * N);
+		build(A);
+	}
+	void pull(int n) { seg[n] = seg[n << 1] + seg[n << 1 | 1]; }
+	void push(int l, int r, int n) {
+		seg[n] = (r - l + 1) * tmp[n];
+		if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n];
+		tmp[n] = 0;
+	}
+	void build(T A[], int l = 0, int r = -1, int n = 1) {
+		if (r == -1) r = N - 1;
+		if (l == r) seg[n] = A[l];
+		else {
+			int m = (l + r) >> 1;
+			build(A, l, m, n << 1), build(A, m + 1, r, n << 1 | 1);
+			pull(n);
+		}
+	}
+	void build(vector<T>& A, int l = 0, int r = -1, int n = 1) {
+		if (r == -1) r = N - 1;
+		if (l == r) seg[n] = A[l];
+		else {
+			int m = (l + r) >> 1;
+			build(A, l, m, n << 1);
+			build(A, m + 1, r, n << 1 | 1);
+			pull(n);
+		}
+	}
+	void update(int x, T v, int l = 0, int r = -1, int n = 1) {
+		if (r == -1) r = N - 1;
+		if (l == r) seg[n] += v;
+		else {
+			int m = (l + r) >> 1;
+			x <= m ? update(x, v, l, m, n << 1) : update(x, v, m + 1, r, n << 1 | 1);
+			pull(n);
+		}
+	}
+	void update(int a, int b, T v, int l = 0, int r = -1, int n = 1) {
+		if (r == -1) r = N - 1;
+		push(n, l, r);
+		if (l > b || r < a) return;
+		if (l >= a && r <= b) {
+			tmp[n] = v;
+			push(n, l, r);
+		}
+		else {
+			int m = (l + r) >> 1;
+			update(a, b, v, l, m, n << 1), update(a, b, v, m + 1, r, n << 1 | 1);
+			pull(n);
+		}
+	}
+	T query(int a, int b, int l = 0, int r = -1, int n = 1) {
+		if (r == -1) r = N - 1;
+		if (l > b || r < a) return 0;
+		push(n, l, r);
+		if (l >= a && r <= b) return seg[n];
+		int m = (l + r) >> 1;
+		return query(a, b, l, m, n << 1) + query(a, b, m + 1, r, n << 1 | 1);
+	}
+};
\ No newline at end of file
diff --git a/Data Structures/union-find_disjoint_set.cpp b/Data Structures/union-find_disjoint_set.cpp
index 68e42be..e9aafe4 100644
--- a/Data Structures/union-find_disjoint_set.cpp
+++ b/Data Structures/union-find_disjoint_set.cpp
@@ -1,27 +1,17 @@
-#include <vector>
-using namespace std;
-
 class UFDS {
-private: int num_sets; vector<int> p, rank, size;
+private: vector<int> p, rank;
 public:
 	UFDS(int N) {
-		num_sets = N;
 		p.assign(N, 0);
 		for (int i = 0; i < N; i++) p[i] = i;
 		rank.assign(N, 0);
-		size.assign(N, 1);
 	}
 	int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); }
 	bool same_set(int i, int j) { return find_set(i) == find_set(j); }
-	int sets() { return num_sets; }
-	int size_set(int i) { return size[find_set(i)]; }
 	void union_set(int i, int j) {
 		if (same_set(i, j)) return;
 		int x = find_set(i), y = find_set(j);
-		if (rank[x] > rank[y]) swap(x, y);
-		p[x] = y;
+		rank[x] > rank[y] ? p[y] = x : p[x] = y;
 		if (rank[x] == rank[y]) rank[y]++;
-		size[y] += size[x];
-		--num_sets;
-	}
-};
+ 	}
+};
\ No newline at end of file