Problem: Dynamic Product of Array Except Self

# Description

Design a data structure that supports two operations on an integer array: updating an element's value, and querying the product of all elements except the one at a specific index. Since the answers can be very large, return the queried products modulo 10^9 + 7. Note that you cannot use the division operation.

Implement the DynamicArray class:

• DynamicArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int getProductExceptSelf(int index) Returns the product of all elements in nums except the element at index, modulo 10^9 + 7.

Example 1:

• Input: ["DynamicArray", "getProductExceptSelf", "update", "getProductExceptSelf"]
• [[[1, 2, 3, 4]], [2], [1, 5], [0]]
• Output: [null, 8, null, 60]
• Explanation:

  DynamicArray dynamicArray = new DynamicArray([1, 2, 3, 4]);
  dynamicArray.getProductExceptSelf(2); // Returns 1 * 2 * 4 = 8
  dynamicArray.update(1, 5);            // nums becomes [1, 5, 3, 4]
  dynamicArray.getProductExceptSelf(0); // Returns 5 * 3 * 4 = 60
  

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 100
• 0 <= index < nums.length
• 1 <= val <= 100
• At most 10^5 calls will be made in total to update and getProductExceptSelf.

---

# key points

이 문제는 Segment tree의 본질을 파악하면 된다. 10만 개의 데이터가 수시로 바뀔 때마다 배열을 다 곱하는 것은 불가능하다. 그래서 세그먼트 트리는 데이터를 '토너먼트 대진표'처럼 쌓아 올려 이 문제를 해결할 수 있다.

첫 번째로는 Building the tree, 세그먼트 트리 구축을 한다. 맨 아래쪽(Leaf)에 원본 배열의 값을 두고 두 개씩 짝을 지어 곱한 값을 그 위의 부모 노드에 저장한다. 이 과정을 하나의 꼭대기(Root, 전체 곱)가 나올 때까지 반복한다.

두 번째는 O(log N)으로 배령의 특정 값을 바꿔준다. 이로 인해 전체 배열을 다 훑을 필요가 없다. 방금 바뀐 그 숫자부터 시작해서, 자신의 부모를 타고 꼭대기까지 올라가는 단 하나의 경로(Path)만 다시 계산해 주면 된다. 대진표의 높이는 log N이므로, 10만 개의 데이터라도 단 17번의 계산이면 업데이트가 끝난다.

세 번째로는 O(log N) 구간 곱 쿼리 (Range Query)이다. 나를 제외한 나머지 곱(Except Self)을 구하려면, 내 인덱스를 기준으로 '왼쪽 구간의 곱'과 '오른쪽 구간의 곱'을 트리의 중간 노드들에서 쏙쏙 뽑아와 곱해주면 끝난다.

---

# Solutions

class DynamicArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.MOD = 10**9 + 7
        
        # Allocate memory for the Segment Tree (2 * n is enough for iterative approach)
        self.tree = [1] * (2 * self.n)
        
        # 1. Insert original array elements into the leaf nodes of the tree
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
            
        # 2. Build the tree by calculating parents from the bottom up
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = (self.tree[i * 2] * self.tree[i * 2 + 1]) % self.MOD

    def update(self, index: int, val: int) -> None:
        # Navigate to the specific leaf node
        pos = index + self.n
        self.tree[pos] = val
        pos //= 2
        
        # Bubble up the changes to the root
        while pos > 0:
            self.tree[pos] = (self.tree[2 * pos] * self.tree[2 * pos + 1]) % self.MOD
            pos //= 2

    def queryRange(self, left: int, right: int) -> int:
        """Helper function: Computes the product in the range [left, right]"""
        l = left + self.n
        r = right + self.n + 1 # +1 because 'right' is inclusive in the query
        res = 1
        
        while l < r:
            # If 'l' is a right child, multiply its value and move to the next subtree
            if l % 2 == 1:
                res = (res * self.tree[l]) % self.MOD
                l += 1
            # If 'r' is a right child, move to the left child and multiply its value
            if r % 2 == 1:
                r -= 1
                res = (res * self.tree[r]) % self.MOD
                
            # Move up to the parents
            l //= 2
            r //= 2
            
        return res

    def getProductExceptSelf(self, index: int) -> int:
        # The product except self is the product of [0, index-1] and [index+1, n-1]
        left_prod = self.queryRange(0, index - 1) if index > 0 else 1
        right_prod = self.queryRange(index + 1, self.n - 1) if index < self.n - 1 else 1
        
        return (left_prod * right_prod) % self.MOD

---