Let’s solve another problem. You are given an array v of length N, where each element is a vector of length k.
Answer two types of queries:
S(i, j): Output v_i + v_i + 1 + v_i + 2 + ... + v_j.
M(i, a₁, a₂, ..., a_k): Set v_i to (v_i1 + a₁, v_i2 + a₂, ..., v_ik + a_k).
This problem can be solved using a binary indexed tree.
Let's reduce the original problem to this using these two observations:
1. Every number T_i in the tree can always be represented as 2^a₁ × 3^a₂ × 5^a₃ × 7^a₄ × 11^a₅ × 13^a₆. Therefore we could store a vector H_i = {a₁, a₂, a₃, a₄, a₅, a₆} in the tree instead of the number itself (Calculating the original number, counting its divisors, and multiplying it with another number using this representation is left as an exercise to the reader).
2. We can reduce subtree queries to range queries on an array using the Euler tour technique.