---
# System prepended metadata

title: data structure
tags: [ADA, CP, DSA]

---

# python data structure and algorithms template
## binary search
![image](https://hackmd.io/_uploads/ryQHOveaC.png)


## 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)
```