Prefix Product||12ms Beats 91.95%
直覺為了確保構造函數以外的方法具有時間複雜度 O(1)，請使用前綴積。
請注意，乘法恆等式為 1，而加法恆等式為 0。
C++ 和 Python 已完成。方法[如有需要請開啟英文字幕]

宣告成員變數

建構函式為稍後呼叫其他方法保留空間
此方法的add設計如下

此方法的getProduct(int k)設計如下
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To ensure the methods have time complexity O(1) except the constructor, use prefix product.
Note that **1 is the multiplication identity** instead of 0 for addition.
C++ & Python are done.

# Approach
<!-- Describe your approach to solving the problem. -->
[Please turn on English subtitles if necessary]
[https://youtu.be/3Um5MFOHZkY?si=HYvJsdJPdVvPzvJu](https://youtu.be/3Um5MFOHZkY?si=HYvJsdJPdVvPzvJu)
1. Declare the member variables
```
vector<int> product={1};// multiplication identity 1
int n=1; // size for vector  product
```
2. The constructor reserves the space for the later calling other methods 
3. the method `add` is so designed
```
// reset, array cannot have 0 for avoiding of divided by 0
if (num==0) { 
    product={1};
    n=1;
}
else{// add a new prefix item & then n++
    product.push_back(product[n++-1]*num);
}
```
4. the method `getProduct(int k)` is so designed
```
if (n<=k)// in this case there is at least 0 for the last k nums
    return 0;
return product[n-1]/product[n-k-1];// product of last k nums
```
5. A variant is made in which the product is declared as a global variable by using static array which has the similar speed
6.  Python code is given in the similar way.
# Note on Prefix Sum
want to compute p=$x_{n-k}\cdots x_{n-1}$. I's to see if some of $x_i$ is 0 then p=0. 
Suppose all $x_i$ are non-zero, then
$$
p=\frac{x_0\cdots x_{n-k-1}x_{n-k}\cdots x_{n-1}}{x_0\cdots x_{_{n-k-1}}}
$$
where product[n-1]=numerator, product[n-k-1]=denominator
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Let $n$ be the number of calling methods
$O(n)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)$
# Code||12ms Beats 91.95%
```cpp []
class ProductOfNumbers {
public:
    vector<int> product={1};
    int n=1;
    ProductOfNumbers(){
        product.reserve(40000);
    }
    
    void add(int num) {
        if (num==0) {
            product={1};
            n=1;
        }
        else{
            product.push_back(product[n++-1]*num);
        }
    }
    
    int getProduct(int k) {
        if (n<=k) return 0;
        return product[n-1]/product[n-k-1];
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */
```
```cpp [C++ 2nd ver]
int product[40000];
class ProductOfNumbers {
public:
    int n=1;
    ProductOfNumbers(){
        product[0]=1;
    }
    
    void add(int num) {
        if (num==0) {
            n=1;
        }
        else{
            product[n]=product[n-1]*num;
            n++;
        }
    }
    
    int getProduct(int k) {
        if (n<=k) return 0;
        return product[n-1]/product[n-k-1];
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */
```
# Python
```
class ProductOfNumbers:

    def __init__(self):
        self.product=[1]
        self.n=1

    def add(self, num: int) -> None:
        if num==0:
            self.product=[1]
            self.n=1
        else:
            self.product.append(self.product[-1]*num)
            self.n+=1

    def getProduct(self, k: int) -> int:
        if self.n<=k:
            return 0
        else:
            return self.product[-1]//self.product[-k-1]
        


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
```
['Prefix Sum', 'C++', 'Python3']