This is the hard follow-up to Find X Value of Array I, and the twist changes everything. In the first version I counted subarrays by product residue in one pass. Here the array mutates: each query first overwrites one element (permanently), then asks a question about a *suffix* of the array. With up to `2 * 10^4` queries against an array of `10^5` elements, I can't re-sweep from scratch every time. I need a structure that supports a point update and a range fold, both cheap. ## What each query actually asks Read the operation carefully. For a query `[index, value, start, x]` I set `nums[index] = value`, drop the prefix `nums[0..start-1]`, and then count the ways to remove a *suffix* while keeping the array non-empty. Keeping a non-empty prefix of `nums[start..n-1]` means choosing an endpoint `j >= start` and keeping `nums[start..j]`. The x-value is how many of those choices give product `≡ x (mod k)`. So each query is: over the segment `[start, n-1]`, count prefixes (of that segment) whose product residue equals `x`. The update is a single-point write. That shape is a segment tree. ## The node summary The saving grace, again, is `k <= 5`. I never store products, only residues. Each segment tree node summarizes its range with two things: - `prod` — the residue of the product of every element in the range. - `mat[a][b]` — how many prefixes *within this range* have product residue `b`, assuming the running product entering the range is residue `a`. `mat` is a `k * k` table, at most `25` integers. The incoming residue `a` matters because a prefix's residue depends on whatever was multiplied in before the range started. A leaf holding element with residue `r` is trivial: the only prefix is the element itself, so for each incoming `a` it lands in bucket `(a * r) % k`. That is `mat[a][(a*r)%k] = 1`, everything else zero, and `prod = r`. ## Merging two children This is the one idea the whole solution rests on. To merge a left child `L` and a right child `R` into a parent, fix an incoming residue `a`: - Prefixes ending inside `L` are counted by `L.mat[a]` directly. - To reach `R`, the running product has first passed through all of `L`, so the residue entering `R` is `p = (a * L.prod) % k`. Prefixes ending inside `R` are then counted by `R.mat[p]`. ``` parent.mat[a][b] = L.mat[a][b] + R.mat[p][b], p = (a * L.prod) % k parent.prod = (L.prod * R.prod) % k ``` Threading `L.prod` into `R`'s incoming index is what makes the merge associative and correct — it's the segment-tree analogue of the `(r * a) % k` step from the easy version, lifted to whole blocks. ## Answering a query An update rewrites one leaf and pulls the `mat`/`prod` back up the path, `O(k^2 log n)`. For the query I fold the nodes covering `[start, n-1]` left to right, carrying the running `(mat, prod)` accumulator and combining with the same merge rule. The empty prefix has product `1`, so the incoming residue at `start` is `1`; the answer is `accumulator.mat[1][x]`. Because I always visit the left child before the right one and only fully-covered nodes contribute, the folds happen in index order, which is exactly what the non-commutative merge requires. ## Why residues are enough Product mod `k` is a congruence: `(x * y) mod k = ((x mod k) * (y mod k)) mod k`. Every element collapses to one of `k` values, every partial product to one of `k` residues, so the `mat` table never grows and the true (astronomically large) products never appear. ## Complexity - Time `O((n + q) * k^2 * log n)`: build is linear in nodes, each update and each query touch `O(log n)` nodes and each merge is `O(k^2)`. With `k <= 5` the `k^2` factor is a small constant. - Space `O(n * k^2)`: the segment tree stores a `k * k` matrix per node. On the worst case (`n = 10^5`, `q = 2 * 10^4`, `k = 5`) this runs in tens of milliseconds locally. ## Code (C++) ```cpp class Solution { public: int K, n; vector prod; vector,5>> mat; array,5> leafMat(int r) { array,5> m{}; for (int a = 0; a < K; ++a) m[a][(a * r) % K] = 1; return m; } void pull(int node) { int l = node*2, r = node*2+1; prod[node] = (prod[l] * prod[r]) % K; auto &L = mat[l], &R = mat[r], &M = mat[node]; for (int a = 0; a < K; ++a) { int p = (a * prod[l]) % K; for (int b = 0; b < K; ++b) M[a][b] = L[a][b] + R[p][b]; } } void build(int node, int lo, int hi, vector& nums) { if (lo == hi) { prod[node] = nums[lo] % K; mat[node] = leafMat(prod[node]); return; } int mid = (lo + hi) / 2; build(node*2, lo, mid, nums); build(node*2+1, mid+1, hi, nums); pull(node); } void update(int node, int lo, int hi, int pos, int val) { if (lo == hi) { prod[node] = val % K; mat[node] = leafMat(prod[node]); return; } int mid = (lo + hi) / 2; if (pos <= mid) update(node*2, lo, mid, pos, val); else update(node*2+1, mid+1, hi, pos, val); pull(node); } array,5> accMat; int accProd; bool accInit; void combine(int node) { if (!accInit) { accMat = mat[node]; accProd = prod[node]; accInit = true; return; } array,5> M{}; auto &L = accMat, &R = mat[node]; for (int a = 0; a < K; ++a) { int p = (a * accProd) % K; for (int b = 0; b < K; ++b) M[a][b] = L[a][b] + R[p][b]; } accMat = M; accProd = (accProd * prod[node]) % K; } void query(int node, int lo, int hi, int ql) { if (ql <= lo) { combine(node); return; } if (ql > hi) return; int mid = (lo + hi) / 2; query(node*2, lo, mid, ql); query(node*2+1, mid+1, hi, ql); } vector resultArray(vector& nums, int k, vector>& queries) { K = k; n = nums.size(); prod.assign(4*n, 0); mat.assign(4*n, array,5>{}); build(1, 0, n-1, nums); vector res; res.reserve(queries.size()); for (auto &q : queries) { update(1, 0, n-1, q[0], q[1]); accInit = false; query(1, 0, n-1, q[2]); res.push_back(accInit ? accMat[1 % K][q[3]] : 0); } return res; } }; ```