leetcode

commit 21316c856a072fb6f21b5c59f24cb65c9fe8060c
parent 5d6cfa885dab203135d66bf59515764164c2927b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 25 Oct 2024 11:57:17 +0200

Add two Segment Tree implementations to Templates

Diffstat:
M
README.md
 | 
18
++++++++++--------
M
Templates/bfs_floodfill_recursive.cpp
 | 
2
--
A
Templates/segment_tree.cpp
 | 
25
+++++++++++++++++++++++++
A
Templates/segment_tree_recursive.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 85 insertions(+), 10 deletions(-)
diff --git a/README.md b/README.md
@@ -6,20 +6,22 @@
 
 In this repo I want to share with you my solutions to some Leetcode problems
 written in C++ to practice my Algorithms and Data Structure skills.  I will
-update this list periodically as I do more problems.  I hope it will be helpful
+update this list periodically as I do more problems. I hope it will be helpful
 to some of you if you get stuck on a specific problem. Feel free to contact me
 if you have any questions.
 
 ## Templates
 
-I have accumulated a list of most commonly used algorithms to serve as a base
-for solving problems.
+I have accumulated a list of most commonly used algorithms to serve as a
+reference and a base for solving problems.
 
-* [MST from edge priority queue](Templates/MST_pq.cpp)
-* [MST from edge vector](Templates/MST_vector.cpp)
-* [Matrix BFS/Flood fill Iterative](Templates/bfs_floodfill.cpp)
-* [Matrix BFS/Flood fill Recursive](Templates/bfs_floodfill_recursive.cpp)
-* [Union Find](Templates/Union_Find.cpp)
+* [MST from edge priority queue](Templates/MST_pq.cpp): Reference implementation
+* [MST from edge vector](Templates/MST_vector.cpp): Reference implementation, edges need to be sorted ascending by len
+* [Matrix BFS/Flood fill Iterative](Templates/bfs_floodfill.cpp): Reference implementation
+* [Matrix BFS/Flood fill Recursive](Templates/bfs_floodfill_recursive.cpp): Reference implementation
+* [Union Find](Templates/Union_Find.cpp): Fast implementation, all optimization tricks used
+* [Segment Tree Iterative](Templates/segment_tree.cpp): Fast implementation, contains tricky bits
+* [Segment Tree Recursive](Templates/segment_tree_recursive.cpp): Reference implementation, easy to understand
 
 ## Problems
 
diff --git a/Templates/bfs_floodfill_recursive.cpp b/Templates/bfs_floodfill_recursive.cpp
@@ -8,8 +8,6 @@ int n, m;
 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
 
 bool dfs(const Matrix &mat, Marked &mark, int a, int b) {
-    if (got == word.size()) return true;
-
     mark[a][b] = true;
     for (auto [oa, ob] : offsets) {
         int x = a + oa, y = b + ob;
diff --git a/Templates/segment_tree.cpp b/Templates/segment_tree.cpp
@@ -0,0 +1,25 @@
+class SegmentTree {
+    const int n;
+    vector<int> t = vector<int>(2 * n);
+
+public:
+    SegmentTree(const vector<int> nums): n(size(nums)) {
+        for (int i = 0; i < n; i++) t[n + i] = nums[i];
+        for (int i = n - 1; i > 0; i--) t[i] = t[i * 2] + t[i * 2 + 1];
+    }
+
+    int sum(int l, int r) const {
+        int res = 0;
+
+        for (l += n, r += n; l < r; l /= 2, r /= 2)  {
+            if (l & 1) res += t[l++];
+            if (r & 1) res += t[--r];
+        }
+
+        return res;
+    }
+
+    void update(int p, int val) {
+        for (t[p += n] = val; p > 1; p /= 2) t[p / 2] = t[p] + t[p ^ 1];
+    }
+};
diff --git a/Templates/segment_tree_recursive.cpp b/Templates/segment_tree_recursive.cpp
@@ -0,0 +1,50 @@
+class SegmentTree {
+    const int n;
+    vector<int> t = vector<int>(4 * n);
+
+    void build(const vector<int>& nums, int idx, int left, int right) {
+        if (left == right) {
+            t[idx] = nums[left];
+            return;
+        }
+
+        const int mid = (left + right) / 2;
+        build(nums, idx * 2, left, mid);
+        build(nums, idx * 2 + 1, mid + 1, right);
+        t[idx] = t[idx * 2] + t[idx * 2 + 1];
+    }
+
+    int sum(int idx, int left, int right, int l, int r) const {
+        if (l > r) return 0;
+        if (l == left && r == right) return t[idx];
+
+        const int mid = (left + right) / 2;
+        return sum(idx * 2, left, mid, l, min(r, mid))
+             + sum(idx * 2 + 1, mid + 1, right, max(l, mid + 1), r);
+    }
+
+    void update(int idx, int left, int right, int pos, int val) {
+        if (left == right) {
+            t[idx] = val;
+            return;
+        }
+
+        const int mid = (left + right) / 2;
+        if (pos <= mid) update(idx * 2, left, mid, pos, val);
+        else update(idx * 2 + 1, mid + 1, right, pos, val);
+        t[idx] = t[idx * 2] + t[idx * 2 + 1];
+    }
+
+public:
+    SegmentTree(const vector<int> nums): n(size(nums)) {
+        build(nums, 1, 0, n - 1);
+    }
+
+    int sum(int left, int right) const {
+        return sum(1, 0, n - 1, left, right);
+    }
+
+    void update(int pos, int val) {
+        update(1, 0, n - 1, pos, val);
+    }
+};