Modulo range sum in a Fenwick tree

general
, , , , ,
1

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

2

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

  2. Have a look here

3

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
4

Only range sum is not all, I got confused and had use BigInteger to solve SEACO

5

Yes I tried this but didn’t work for some reason, maybe just a small mistake then, Thanks :slight_smile:

6

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.

7

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