Range Product Queries Of Powers - Leetcode Solution

The "Range Product Queries Of Powers" problem on LeetCode asks us to design an algorithm to support two operations on an array of integer numbers:

• Update(i, val): update the ith element of the array to be val.
• Product(left, right): return the product of all elements in the subarray [left, right].

In this problem, the array is full of integer numbers, but each element is a power of a fixed base. In other words, each element of the array is of the form base^a_i, where a_i is an integer. The base is a fixed positive integer.

We can solve this problem by using a data structure called a segment tree. A segment tree is a binary tree that divides an array into segments and represents each segment as a node in the tree. Each node in the tree stores some information about the segment it represents, such as the sum, the maximum, the minimum, or the product of all elements in the segment.

To apply a segment tree to this problem, we can define a node in the tree to store the product of all elements in the segment it represents. The root of the tree represents the full array, and each leaf node represents a single element of the array. To build the segment tree, we can use a recursive procedure that starts from the root and divides the array into two halves until each leaf node represents a single element.

To update an element of the array, we need to propagate the change to all nodes in the segment tree that represent the segment that contains the updated element. We can do this by visiting each node from the root down to the leaf that represents the updated element, updating its product value from its children nodes.

To compute the product of a subarray, we need to traverse the segment tree from the root down to the nodes that represent the segments that overlap with the requested subarray. We can do this recursively, checking if each segment is fully contained in the requested subarray, partially contained, or disjoint. If a segment is fully contained, we can return its product value. If a segment is disjoint, we can return 1 (the neutral element for the product operation). If a segment is partially contained, we need to recursively compute the product of its children nodes that are fully contained in the requested subarray.

Here's the Python code for the solution:

class SegmentTree:
    def __init__(self, arr, base):
        self.arr = arr
        self.base = base
        self.tree = [0] * (4 * len(arr))
        self.build(0, 0, len(arr) - 1)

    def build(self, i, left, right):
        if left == right:
            self.tree[i] = self.arr[left]
        else:
            mid = (left + right) // 2
            self.build(2 * i + 1, left, mid)
            self.build(2 * i + 2, mid + 1, right)
            self.tree[i] = self.tree[2 * i + 1] * self.tree[2 * i + 2]

    def update(self, i, val):
        self._update(0, 0, len(self.arr) - 1, i, val)

    def _update(self, node, left, right, i, val):
        if left == right:
            self.tree[node] = val
        else:
            mid = (left + right) // 2
            if i <= mid:
                self._update(2 * node + 1, left, mid, i, val)
            else:
                self._update(2 * node + 2, mid + 1, right, i, val)
            self.tree[node] = self.tree[2 * node + 1] * self.tree[2 * node + 2]

    def query(self, left, right):
        return self._query(0, 0, len(self.arr) - 1, left, right)

    def _query(self, node, left, right, qleft, qright):
        if qleft > right or qright < left:
            return 1
        if qleft <= left and right <= qright:
            return self.tree[node]
        mid = (left + right) // 2
        return self._query(2 * node + 1, left, mid, qleft, qright) * self._query(2 * node + 2, mid + 1, right, qleft, qright)

class Solution:
    def __init__(self, arr: List[int], base: int):
        self.stree = SegmentTree(arr, base)

    def update(self, i: int, val: int) -> None:
        self.stree.update(i, val)

    def product(self, left: int, right: int) -> int:
        return self.stree.query(left, right)

The time complexity of this solution is O(n log n) for building the segment tree and O(log n) for each update and query operation. The space complexity is O(n log n) for the segment tree.

1