Python O(1) query by Prefix product. 85%+ [ With explanation ]
Python O(1) query by prefix product\n\n---\n\nHint:\n#1.\nRecall the technique of prefix sum in Leetcode #303 Range Sum Query - Immutable.\n\n#2.\nSimilarly, te
Python O(1) query by prefix product\n\n---\n\n**Hint**:\n#1.\nRecall the technique of prefix sum in [Leetcode #303 Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/).\n\n#2.\nSimilarly, technique of Prefix product also applies to Range Product Query.\n\n#3.\nBe careful to special case: add() operation with 0.\n\n---\n\n**Algorithm**:\n\nStep_#1.\nBuild a **product table**, initialized to [1], in order to speed up **range product query** of **last k elements**.\n\n---\n\nStep_#2.\n**Update product table** when **add**( **num**: int ) **function is called**.\n\n#2-a.\nIf *num* is non-zero,\nmultiply *previous product* with *num*, and append to product table on the tail.\n\n#2-b.\n**If *num* is 0**,\n**clear and reset product table to [1]**.\n\n---\n\nStep_#3:\nResponse to getProduct( k: int) query.\n\nIf k >= size of product table, which means that last k elements include at least one zero, return 0.\n\nOtherwise, lookup product table and compute the range product for last k elements\n\n\n---\n\n```\nclass ProductOfNumbers:\n\n    def __init__(self):\n        \n        self.product_table = [1]\n        \n    def add(self, num: int) -> None:\n        \n        if num != 0:\n            # update product table if num is non-zero.\n            self.product_table.append( num * self.product_table[-1] )\n        else:\n            # reset product table after 0 is insert\n            self.product_table = [1]\n\n            \n            \n    def getProduct(self, k: int) -> int:\n        \n        if k >= len( self.product_table ):\n            #  last k elements include at least one zero, which was inserted before getProduct() query\n            return 0\n        else:\n            # compute the product of last k elemetns by look-up table\n            return self.product_table[-1] // self.product_table[-(k+1)]\n```\n\n---\n\nRelated leetcode challenge:\n[Leetcode #303 Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/)
['Dynamic Programming', 'Memoization', 'Python']