Modulo range sum in a Fenwick tree

How to return the sum over a range modulo M in a Fenwick tree?

  1. You dont honestly need Fenwick tree. Just a simple prefix sum array will do.

  2. 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).

1 Like

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 :slight_smile:

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

1 Like