以下是 LeetCode 3525「求出数组的 X 值 II」的 Java 实现。

解题思路

这道题的关键在于理解查询的本质：

1. 更新 `nums[index]` 为 `value`
2. 移除前缀 `nums[0..start-1]`，得到子数组 `nums[start..n-1]`
3. 移除任意后缀（可空，但不能删完），使得剩余元素乘积 `% k == x`

第 3 步等价于：统计子数组 `nums[start..n-1]` 的所有非空前缀中，乘积模 `k` 等于 `x` 的个数。

由于 `k ≤ 5` 极小，可以用 线段树 维护每个区间的信息：

节点属性    含义    
`prod`    区间内所有元素乘积 `% k`    
`remain[r]`    区间内非空前缀中，乘积 `% k == r` 的个数    

合并两个子节点 `[L,M]` 和 `[M+1,R]`：
- 完全在左子树的前缀：`left.remain[r]`
- 跨越左右子树的前缀：`left.prod * (右子树前缀乘积) % k`

---

Java 代码

```java
class Solution {
    /**
     * 线段树节点
     * prod: 区间内所有元素乘积 % k
     * remain[r]: 非空前缀中乘积 % k == r 的个数
     */
    static class Node {
        int prod;           // 区间乘积 % k
        int[] remain;       // remain[r] = 前缀乘积 % k == r 的个数
        
        Node(int k) {
            this.prod = 1;  // 乘法单位元
            this.remain = new int[k];
        }
    }
    
    static class SegmentTree {
        int n, k;
        Node[] tree;
        
        SegmentTree(int[] nums, int k) {
            this.n = nums.length;
            this.k = k;
            this.tree = new Node[4 * n];
            build(nums, 0, 0, n - 1);
        }
        
        void build(int[] nums, int node, int l, int r) {
            tree[node] = new Node(k);
            if (l == r) {
                int val = nums[l] % k;
                tree[node].prod = val;
                tree[node].remain[val] = 1;
                return;
            }
            int mid = (l + r) / 2;
            build(nums, 2 * node + 1, l, mid);
            build(nums, 2 * node + 2, mid + 1, r);
            tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
        }
        
        /**
         * 合并左右子节点
         * 
         * 对于区间 [L,R]，左子 [L,M]，右子 [M+1,R]：
         * - 完全在左子树的前缀：left.remain
         * - 跨越左右的前缀：left.prod * (右子树前缀) % k
         */
        Node merge(Node left, Node right) {
            Node res = new Node(k);
            res.prod = (left.prod * right.prod) % k;
            
            // 完全在左子树的前缀
            for (int i = 0; i < k; i++) {
                res.remain[i] = left.remain[i];
            }
            
            // 跨越左右子树的前缀
            for (int r = 0; r < k; r++) {
                int newResidue = (left.prod * r) % k;
                res.remain[newResidue] += right.remain[r];
            }
            
            return res;
        }
        
        void update(int idx, int val) {
            update(0, 0, n - 1, idx, val);
        }
        
        void update(int node, int l, int r, int idx, int val) {
            if (l == r) {
                int v = val % k;
                tree[node].prod = v;
                for (int i = 0; i < k; i++) {
                    tree[node].remain[i] = 0;
                }
                tree[node].remain[v] = 1;
                return;
            }
            int mid = (l + r) / 2;
            if (idx <= mid) {
                update(2 * node + 1, l, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, r, idx, val);
            }
            tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
        }
        
        Node query(int ql, int qr) {
            return query(0, 0, n - 1, ql, qr);
        }
        
        Node query(int node, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) {
                return tree[node];
            }
            if (r < ql || l > qr) {
                return new Node(k); // 单位元：prod=1, remain 全 0
            }
            int mid = (l + r) / 2;
            Node left = query(2 * node + 1, l, mid, ql, qr);
            Node right = query(2 * node + 2, mid + 1, r, ql, qr);
            return merge(left, right);
        }
    }
    
    public int[] resultArray(int[] nums, int k, int[][] queries) {
        // 预处理：所有数先 % k，防止线段树内溢出
        int[] modNums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            modNums[i] = nums[i] % k;
        }
        
        SegmentTree segTree = new SegmentTree(modNums, k);
        int[] ans = new int[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            int idx = queries[i][0];
            int val = queries[i][1] % k;
            int start = queries[i][2];
            int x = queries[i][3];
            
            segTree.update(idx, val);
            Node res = segTree.query(start, nums.length - 1);
            ans[i] = res.remain[x];
        }
        
        return ans;
    }
}
```

---

复杂度分析

指标    复杂度    说明    
建树    O(n)    每个节点 O(k) 合并，k ≤ 5 为常数    
单点更新    O(log n)    线段树标准更新    
区间查询    O(log n)    线段树标准查询    
总时间    O(n + q · log n)    q = queries.length    
空间    O(n · k)    线段树 4n 个节点，每个节点 O(k)    

下载文件：[Solution_3525.java](sandbox:///mnt/agents/output/Solution_3525.java)