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

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` `面試`