We have an array( $$$a$$$ ) of length $$$n$$$, all the elements are less than or equal to $$$n$$$, then we have to answer $$$q$$$ queries, each will be three numbers $$$x$$$, $$$l$$$, $$$r$$$, then you have to print $$$\displaystyle\sum\limits_{l \le i mod x \le r}a_i$$$, i.e print the sum of all $$$a_i$$$ for $$$1 \le i \le n$$$ and $$$i$$$ mod $$$x$$$ is in range $$$[l \cdot \cdot r]$$$.
$$$0 \le l \le r < x \le n$$$
Then what if we had queries to add a range?
The first query can be changed a little bit, it can be like we have $$$k$$$, $$$x$$$, $$$l$$$, $$$r$$$, then print the same number but with $$$i > k$$$.
$$$0 \le k < n$$$
Please share the solutions.
Your problem is similar to this with point updates, and $$$l = r$$$ for queries.
For each $$$x <= \sqrt{n}$$$ create a fenwick tree in which the $$$j$$$ th position stores $$$\sum_{i mod x = j} a_i$$$. Note that it is easy handle range updates because every range modulo $$$x$$$ can be broken into atmost three ranges, prefix of $$$[x]$$$, suffix of $$$[x]$$$, complete $$$[x]$$$ (maybe more than once).
To handle $$$x > \sqrt{n}$$$ we just keep the fenwick tree over an actual array and when answering a query we need to ask atmost $$$n/x < \sqrt{n}$$$ range queries from fenwick tree.
Each query this way can be answered in $$$O(\sqrt{n} log n)$$$
Nice heavy-light + data structure solution, thank you. There is one more unsolved part, what can we do if the update queries are modular segments(i.e. update all indices such that $$$i$$$ mod $$$x$$$ is in range $$$[l..r]$$$)
Assuming there is no updating query: Let $$$ps$$$ be the array of partial sums. Then we are asking for:
$$$[\sum_{i \mod x = r}ps_i] - [\sum_{i \mod x = l - 1}ps_{i}]$$$
Then the problem reduces to this problem:
Having an array, we ask for sum of elements with indices $$$i \mod x = l$$$ which $$$x, l$$$ is given in the query. This can be solved by precalculating value $$$S_{x, y} = \sum_{i \mod x = y}ps_i$$$ for $$$x < \sqrt n$$$ and bruteforce for $$$x > \sqrt n$$$ when the query comes.
Now for updating query, you can do point updates (I have no idea for range updates). Point updates become range update on partial sum array, and as described by fugazi, you can easily update the value $$$S_{x, y}$$$ using fenwick tree for each $$$x < \sqrt n$$$.
Nice, both range queries that i asked for are still unsolved, hope one could help me with it.