POTIONS-Potions Class

Potions Class

Below given python code for potions spoj or potions class spoj.
In question a function is given for range query and seeing the number of query(q<100000) every query should be done in constant time O(1).Now having a look on function and trying to simplify it.

Now “w” is constant so taking it outside of summation

Now subtracting and adding “x” to  “i”  sp,

Now rearranging the above we get  

Since “x” is constant so taking it out of summation and taking common with

Now owr answer will be :..

If you have any problem in understanding the above logic you can mail me @ raj.nishant360@gmail.com

Below is Python 2.7 implementation of above logic.

import sys
t=int(sys.stdin.readline())
while t:
    n,q=map(int,sys.stdin.readline().split())
    s=raw_input().split()
    cum=[]
    cum2=[]
    for i in range(0,n+1):
        cum.append(0)
        cum2.append(0)
    for i in range(1,n+1):
        cum[i]=cum[i-1] + int(s[i-1])
        cum2[i]=cum2[i-1]+i*(int(s[i-1]))
    for i in range(0,q):
        w,x,y,z=map(int,sys.stdin.readline().split())
        lower = y+x
        higher = z+x
        result=(cum2[higher]-cum2[lower-1] + (w-x)*(cum[higher]-cum[lower-1]))%1000000007
        sys.stdout.write(str(result))
        sys.stdout.write("\n")
    t=t-1