leetcode

commit c35d611a2230cbf4ee0da919689d3aface3301f5
parent 6001ccf563bb24b7cbef75bfebea9504274012c2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 29 Oct 2024 16:22:51 +0100

Add Dynamic Segment Tree Recursive implementation

Diffstat:
M
README.md
 | 
1
+
A
Templates/segment_tree_dynamic_recursive.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 51 insertions(+), 0 deletions(-)
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ reference and a base for solving problems.
 * [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
+* [Dynamic Segment Tree Recursive](Templates/segment_tree_dynamic_recursive.cpp): Reference implementation, checks range coverage
 
 ## Problems
 
diff --git a/Templates/segment_tree_dynamic_recursive.cpp b/Templates/segment_tree_dynamic_recursive.cpp
@@ -0,0 +1,50 @@
+class SegmentTree {
+    struct Node {
+        Node *left = nullptr;
+        Node *right = nullptr;
+        int low;
+        int high;
+        int value;
+
+        Node (int low, int high, int value): low(low), high(high), value(value) {}
+    } root;
+
+    void update(Node *root, int l, int r, int val) {
+        if(root->low == l && root->high == r)
+        {
+            root->value = val;
+            root->left = root->right = NULL; // memory leak
+            return;
+        }
+
+        const int mid = root->low + (root->high - root->low) / 2;
+
+        if(!root->left)
+        {
+            root->left = new Node(root->low, mid, root->value);
+            root->right = new Node(mid + 1, root->high, root->value);
+        }
+
+        if(r <= mid) update(root->left, l, r, val);
+        else if(l > mid) update(root->right, l, r, val);
+        else update(root->left, l, mid, val), update(root->right, mid + 1, r, val);
+        root->value = root->left->value && root->right->value;
+    }
+
+    bool query(const Node *root, int l, int r) const {
+        if(!root->left) return root->value;
+        if(root->low == l && root->high == r)  return root->value;
+
+        const int mid = root->low + (root->high - root->low) / 2;
+
+        if(r <= mid) return query(root->left, l, r);
+        else if(l > mid) return query(root->right, l, r);
+        return query(root->left, l, mid) && query(root->right, mid + 1, r);
+    }
+
+public:
+    SegmentTree(int l, int r, int val): root(l, r, val) {}
+
+    void update(int l, int r, int val) { return update(&root, l, r, val); }
+    bool query(int l, int r) const { return query(&root, l, r); }
+};