aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rwxr-xr-x307/main.py95
1 files changed, 95 insertions, 0 deletions
diff --git a/307/main.py b/307/main.py
new file mode 100755
index 0000000..47a9410
--- /dev/null
+++ b/307/main.py
@@ -0,0 +1,95 @@
+#!/usr/bin/env python3
+"""307"""
+
+from typing import List
+
+
+class NumArray_Naive:
+ """Naive implementation. Useless."""
+
+ def __init__(self, nums: List[int]):
+ self.nums = nums
+
+ def update(self, index: int, val: int) -> None:
+ """Update."""
+ self.nums[index] = val
+
+ def sumRange(self, left: int, right: int) -> int:
+ """sumRange."""
+ return sum(self.nums[left : right + 1])
+
+
+class NumArray:
+ """Segment Tree implementation."""
+
+ def __init__(self, nums: List[int]):
+ self.nums = nums
+ self.n = len(nums)
+ self.segment_tree = [0] * (len(nums) * 2)
+ self.build_segment_tree()
+
+ def build_segment_tree(self):
+ """build segment tree."""
+ for i, j in zip(range(self.n, 2 * self.n), range(0, len(self.nums))):
+ self.segment_tree[i] = self.nums[j]
+ for i in reversed(range(1, self.n)):
+ self.segment_tree[i] = (
+ self.segment_tree[i * 2] + self.segment_tree[i * 2 + 1]
+ )
+ # print(self.segment_tree)
+
+ def update_segment_tree(self, index: int, val: int):
+ """update segment tree."""
+ pos: int = index + self.n
+ self.segment_tree[pos] = val
+ while pos > 0:
+ left = pos
+ right = pos
+ if pos % 2 == 0:
+ right = pos + 1
+ else:
+ left = pos - 1
+ self.segment_tree[int(pos / 2)] = (
+ self.segment_tree[left] + self.segment_tree[right]
+ )
+ pos = int(pos / 2)
+
+ def update(self, index: int, val: int) -> None:
+ """Update."""
+ self.update_segment_tree(index, val)
+
+ def sumRange(self, left: int, right: int) -> int:
+ """sumRange."""
+ l = left + self.n
+ r = right + self.n
+ s: int = 0
+
+ while l <= r:
+ if (l % 2) == 1:
+ s += self.segment_tree[l]
+ l += 1
+ if (r % 2) == 0:
+ s += self.segment_tree[r]
+ r -= 1
+ l = int(l / 2)
+ r = int(r / 2)
+
+ return s
+
+
+# Your NumArray object will be instantiated and called as such:
+# obj = NumArray(nums)
+# obj.update(index,val)
+# param_2 = obj.sumRange(left,right)
+
+
+def main():
+ """Main."""
+ num_array = NumArray([1, 3, 5])
+ print(num_array.sumRange(0, 2))
+ num_array.update(1, 2)
+ print(num_array.sumRange(0, 2))
+
+
+if __name__ == "__main__":
+ main()