How to return the sum over a range modulo M in a Fenwick tree?
You dont honestly need Fenwick tree. Just a simple prefix sum array will do.
Have a look here
Is modulo M fixed for all queries? If yes, you can simply use usual Fenwick tree, but store all values modulo M during updates.
So sum over a range will be (sum(r) - sum(l - 1) + M) mod M (I assume that all calculations are done modulo M already).
Only range sum is not all, I got confused and had use BigInteger to solve SEACO
Yes I tried this but didn’t work for some reason, maybe just a small mistake then, Thanks
Oh…Please tell the relevant problem in that case! Assuming question to be asking SEACO and typical “range sum query” have a huge difference XD.
If you are asking this for SEACO, I used 2 segment tree, first I calculated the number of times every 1-type query will repeat, this number was also saved after mod operation.
Then I again used mod operation when updating the array, to have a detailed view of how to return the sum over a range modulo M in a Fenwick/Segment tree have a look at my code here