---
# System prepended metadata

title: code tpl
tags: [mock interview, 面試]

---

# code tpl

{%hackmd theme-dark %}
[2, 3, 5, 6]
    ^     ^
    
 #   1-4
 #   (0-4) - (0-1) = 
 N = number of array
 TC(N)
 SC(N)
 
 
 
 
 1-6

 [], int start, int end,
 
 loop s to end:
   ans+=
 N = number of array
 TC(N)
 SC(1)
 
 
 
 [[1, 2, 3], [4, 5, 6]]
 => [1 2 3 4 5 6]
 
 [1, 2],    3, 5] <
 [2, 3],    4, 6] <
 
 [4, 5, [7*, 9*]] 
 [1, 2, [3*, 5*]] 
 [1, 2, [3*, 5*]] 
 
 prefix(x2, y2) -  prefix(x1, y1)
 
 for x1 to x2:
     for y1 to y2:
      ans+=item
 
 x1:2, y1:2, x2:3, y2:3
 [                ]                   ]
 [                ]                   ]
 [                ](x1, y1)    (x1, y2)
 [  (0-x2, 0-y1-1)](x2, y1)    (x2, y2)
```python=
Class Test:
    #N = number of array
    # TC O(N)
    def init(self, arr):
        # [1, 2, 3, 4]
        # contruct prefix sum array
        prefix = 0
        self.prefixSum = []
        for n in arr:
            prefix += n # 1+2
            self.prefixSum.append(prefix)
            #[1, 3, 6, 10]
            
        

    # getRange so many times
    # TC O(1)
    def getRange(self, x1, y1, x2, y2):
        idx1D = getIdx(x1, y1)
        # 1, 2
        # 3, 3
        endSum = self.prefixSum[end] #10
        pre = start-1 # 2
        if pre == -1: 
            startSum = 0 
        else:
            startSum = self.prefixSum[pre] #1 , 6
        
        return endSum - startSum # 1-0=1, 6-1=5, 10-6=4

```

###### tags: `mock interview` `面試`