how to find sum%(10^9+7) in a given range of array efficiently

general
1

ex
3,4,5,6,7,2
quary l=2,r=5
for i=l to r
ans=(ans+Arr[i])%mod;

2

Make another array, say prefixSumArray[], which contains the (prefix sum % mod) of the array.
This means that prefixSumArray[i] is the sum from 1 to i.
Then for every query from l to r, print prefixSumArray[r] - prefixSumArray[l-1].

Note : I’ll assume 1-indexed array.

For your given array: 3,4,5,6,7,2

PrefixSumArray: 3,7,12,18,25,27

for l=2,r=5 : Answer is prefixSumArray[5] - prefixSumArray[1] = 25-3 = 22.
This works in O(1) for every query with preprocessing time O(N), N : size of the array.

Hope this helps.

3

use Fenwick Tree (BIT)

4

@utsav12071997 the approach given by you is correct,but answer may be negative as we are storing prefix sum % 10^9+7.
So correct way to do that is ( prefixSumArray[5] - prefixSumArray[1] + MOD) %MOD