algorithms

commit df6491e806461115e38795f271aa115dd36273f0
parent d10cb4dc4b88678c5b802ad76b083c08e1bcd61f
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 10 Sep 2026 15:38:55 -0500

Naive segment tree without optimized updates

Diffstat:
M
plan.txt
 | 
4
++--
A
range-sum-query-mutable/range-sum-query-mutable.py
 | 
80
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 82 insertions(+), 2 deletions(-)
diff --git a/plan.txt b/plan.txt
@@ -4,5 +4,5 @@ these are the things I want to learn, ordered
     x number of palindrome substrings (similar to interview where print out all palindrome's len >= 3)
     x prim's algo (visualized in python)
     x permutation problem (similar to interview where print all permutations of a string where only certain chars may be moved)
-    - kahn's algo (visualized in python)
-    - union find
+    x union find
+    - segment tree
diff --git a/range-sum-query-mutable/range-sum-query-mutable.py b/range-sum-query-mutable/range-sum-query-mutable.py
@@ -0,0 +1,80 @@
+class Node:
+    def __init__(self):
+        self.rng = [0, 0]
+        self.rv = 0
+        self.left = None
+        self.right = None
+
+def combine(a,b):
+    root = Node()
+    root.left = a
+    root.right = b
+    root.rv = a.rv + b.rv
+    root.rng[0] = min(a.rng[0], b.rng[0])
+    root.rng[1] = max(a.rng[1], b.rng[1])
+    return root
+
+
+# cases:
+    # if no overlap between rng and root return
+    # if same, return val
+    # if different return sum of left + right
+
+def find_sum(rng, root):
+    if root is None:
+        return 0
+    if rng[1] < root.rng[0] or rng[0] > root.rng[1]:
+        return 0
+    
+    if root.rng[0] >= rng[0] and root.rng[1] <= rng[1]:
+        return root.rv
+    
+    return find_sum(rng,root.left) + find_sum(rng,root.right)
+
+def make_segment(nums):
+    forest = []
+
+    idx = 0
+    for num in nums:
+        current = Node()
+        current.rng = [idx,idx]
+        current.rv = num
+        forest.append(current)
+        idx += 1
+    
+    while len(forest) > 1:
+        nf = []
+
+        for i in range(0, len(forest), 2):
+            if i + 1 < len(forest):
+                nf.append(combine(forest[i], forest[i + 1]))
+            else:
+                nf.append(forest[i])
+
+        forest = nf
+
+    return forest[0]
+
+class NumArray:
+
+    # len(nums) is at most 30_000
+    def __init__(self, nums: List[int]):
+        self.nums = nums
+        self.segment_tree = make_segment(nums)
+        
+    # nums[index] = val 
+    def update(self, index: int, val: int) -> None:
+        self.nums[index] = val
+        self.segment_tree = make_segment(self.nums)
+        return
+
+    # range queries can be size of nums
+    # precondition: left <= right
+    # return: sum(nums[left,right]) - inclusive of left and right
+    def sumRange(self, left: int, right: int) -> int:
+        return find_sum([left,right], self.segment_tree)
+
+# Your NumArray object will be instantiated and called as such:
+# obj = NumArray(nums)
+# obj.update(index,val)
+# param_2 = obj.sumRange(left,right)