# python data structure and algorithms template
## binary search
## Sparse table
```python=
n, q = mii()
l = lii()
sparse_table = [[inf]*int(log2(n) + 1) for _ in range(n)
for i in range(n):
sparse_table[i][0] = l[i]
for i in range(1, int(log2(n) + 1)):
move = 1 << (i - 1)
for j in range(n):
#print(j, move*2)
if j + (1 << i) > n:
#print("break")
break
sparse_table[j][i] = min(sparse_table[j][i - 1], sparse_table[j + (1 << (i - 1))][i - 1])
#print(sparse_table)
query = lii1r(q)
for start, end in query:
diff = end - start + 1
log_diff = int(log2(diff))
#print(start, end, int(log2(diff)), (log2(diff)))
print(min(sparse_table[start][log_diff], sparse_table[end - (1 << log_diff) + 1][log_diff]))
```
## Max_queue
``` python
class max_queue():
def __init__(self):
self.st1 = []
self.st2 = []
def get_max(self):
if not self.st1:
return self.st2[-1][1]
elif not self.st2:
return self.st1[-1][1]
else:
return max(self.st2[-1][1], self.st1[-1][1])
def pop(self):
if self.st2:
self.st2.pop()
else:
max_ele = self.st1[-1][0]
while self.st1:
max_ele = max(self.st1[-1][0], max_ele)
self.st2.append([self.st1[-1][0], max_ele])
self.st1.pop()
self.st2.pop()
def push(self, x):
if self.st1:
self.st1.append([x, max(x, self.st1[-1][1])])
else:
self.st1.append([x, x])
```
## Trie
``` python
class Trie:
class Node:
def __init__(self):
self.child={}
self.end=False
def __init__(self):
self.root=self.Node()
def insert(self, word):
current=self.root
for c in word:
if c not in current.child:
current.child[c]=self.Node()
current=current.child[c]
current.end=True
def search(self, word):
current=self.root
for c in word:
if c not in current.child:
return False
current=current.child[c]
return current.end
```
## Disjoint set
```python
class disjoint_set:
def __init__(self,initial_node_num):
self.parents=[i for i in range(initial_node_num)]
def union(self,node1,node2):
if self.find_parent(node1)!=self.find_parent(node2):
self.parents[self.find_parent(node1)]=self.find_parent(node2)
def find_parent(self,node):
if node!=self.parents[node]:
self.parents[node]=self.find_parent(self.parents[node])
return self.parents[node]
```
## Segment Tree
```python=
class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
#helper function to create the tree from input array
def createTree(nums, l, r):
#base case
if l > r:
return None
#leaf node
if l == r:
n = Node(l, r)
n.total = nums[l]
return n
mid = (l + r) // 2
root = Node(l, r)
#recursively build the Segment tree
root.left = createTree(nums, l, mid)
root.right = createTree(nums, mid+1, r)
#Total stores the sum of all leaves under root
#i.e. those elements lying between (start, end)
root.total = root.left.total + root.right.total
return root
self.root = createTree(nums, 0, len(nums)-1)
def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
#Helper function to update a value
def updateVal(root, i, val):
#Base case. The actual value will be updated in a leaf.
#The total is then propogated upwards
if root.start == root.end:
root.total = val
return val
mid = (root.start + root.end) // 2
#If the index is less than the mid, that leaf must be in the left subtree
if i <= mid:
updateVal(root.left, i, val)
#Otherwise, the right subtree
else:
updateVal(root.right, i, val)
#Propogate the changes after recursive call returns
root.total = root.left.total + root.right.total
return root.total
return updateVal(self.root, i, val)
def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
#Helper function to calculate range sum
def rangeSum(root, i, j):
#If the range exactly matches the root, we already have the sum
if root.start == i and root.end == j:
return root.total
mid = (root.start + root.end) // 2
#If end of the range is less than the mid, the entire interval lies
#in the left subtree
if j <= mid:
return rangeSum(root.left, i, j)
#If start of the interval is greater than mid, the entire inteval lies
#in the right subtree
elif i >= mid + 1:
return rangeSum(root.right, i, j)
#Otherwise, the interval is split. So we calculate the sum recursively,
#by splitting the interval
else:
return rangeSum(root.left, i, mid) + rangeSum(root.right, mid+1, j)
return rangeSum(self.root, i, j)
```
## Segment Tree
```python=
class Node:
def __init__(self, start, end):
# both side inclusive
self.start = start
self.end = end
self.val = 0
self.left = None
self.right = None
class Tree:
def __init__(self, nums):
def create_tree(nums, start, end):
current = Node(start, end)
if start == end:
current.val = nums[start]
return current
mid = (start + end)//2
current.left = create_tree(nums, start, mid)
current.right = create_tree(nums, mid + 1, end)
current.val = current.left.val + current.right.val
return current
self.root = create_tree(nums, 0, len(nums) - 1)
def update(self, i, val):
def update(root, i, val):
if root.start == root.end:
root.val = val
return val
mid = (root.start + root.end) // 2
if i <= mid:
update(root.left, i, val)
else:
update(root.right, i, val)
root.val = root.left.val + root.right.val
return root.val
return update(self.root, i, val)
def query_range(self, left, right):
def query(root, left, right):
if left == root.start and right == root.end:
return root.val
mid = (root.start + root.end) // 2
if right <= mid:
return query(root.left, left, right)
elif left > mid:
return query(root.right, left, right)
else:
return query(root.left, left, mid) + query(root.right, mid + 1, right)
return query(self.root, left, right)
tree = Tree(nums)
```
# Algorithm
## prime fac
```python=
def primeFac(n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d) # supposing you want multiple factors repeated
n //= d
d += 1
if n > 1:
primfac.append(n)
return primfac
```
## Sieve algorithm
```python=
def SieveOfEratosthenes(num):
prime = [True for i in range(num+1)]
prime[0] = prime[1] = False
p = 2
while (p * p <= num):
if (prime[p] == True):
for i in range(p * p, num+1, p):
prime[i] = False
p += 1
return prime
```
## kmp
```python=
def compute_lps(pattern: str) -> List[int]:
# Longest Proper Prefix that is suffix array
lps = [0] * len(pattern)
prefi = 0
for i in range(1, len(pattern)):
# Phase 3: roll the prefix pointer back until match or
# beginning of pattern is reached
while prefi and pattern[i] != pattern[prefi]:
prefi = lps[prefi - 1]
# Phase 2: if match, record the LSP for the current `i`
# and move prefix pointer
if pattern[prefi] == pattern[i]:
prefi += 1
lps[i] = prefi
# Phase 1: is implicit here because of the for loop and
# conditions considered above
return lps
def kmp(pattern: str, text: str) -> List[int]:
match_indices = []
pattern_lps = compute_lps(pattern)
patterni = 0
for i, ch in enumerate(text):
# Phase 3: if a mismatch was found, roll back the pattern
# index using the information in LPS
while patterni and pattern[patterni] != ch:
patterni = pattern_lps[patterni - 1]
# Phase 2: if match
if pattern[patterni] == ch:
# If the end of a pattern is reached, record a result
# and use infromation in LSP array to shift the index
if patterni == len(pattern) - 1:
match_indices.append(i - patterni)
patterni = pattern_lps[patterni]
else:
# Move the pattern index forward
patterni += 1
# Phase 1: is implicit here because of the for loop and
# conditions considered above
return match_indices
```
### z_algorithm
```python=
def z_arr(s):
"""An advanced computation of Z-values of a string."""
# From https://ivanyu.me/blog/2013/10/15/z-algorithm/
Z = [0] * len(s)
Z[0] = len(s)
rt = 0
lt = 0
for k in range(1, len(s)):
if k > rt:
# If k is outside the current Z-box, do naive computation.
n = 0
while n + k < len(s) and s[n] == s[n+k]:
n += 1
Z[k] = n
if n > 0:
lt = k
rt = k+n-1
else:
# If k is inside the current Z-box, consider two cases.
p = k - lt # Pair index.
right_part_len = rt - k + 1
if Z[p] < right_part_len:
Z[k] = Z[p]
else:
i = rt + 1
while i < len(s) and s[i] == s[i - k]:
i += 1
Z[k] = i - k
lt = k
rt = i - 1
return Z
```
## mod inverse
$a \cdot x \equiv 1 \pmod{m}$ find x
use Fermats Little theorem:
If `m` is **prime** and `gcd(a, m) = 1`, then: $a^{m-1} \equiv 1 \pmod{m}$
thus $a^{m-2} \equiv a^{-1} \pmod{m}$
```python
pow(a, m - 2, m)
```
Sign in with Wallet
Connect another wallet