How to improve time complexity of depicted python program

Question

I want to optimize this code but I have no idea how to do further optimization. Here is an example of the input:

3 #size of array  
3 4 3 #data in array  
6 # number of commands  
C 1 2  
C 1 3  
C 3 3  
U 1 4  
C 1 3  
C 1 2  

'C' and 'U' refer to the following operations:

C X Y : Compute the value of F( A[X] ) + F( A[X + 1] ) + F( A[X + 2] ) + .... + F( A[Y] ) (mod 10^9 + 7)
U X Y: Update the element of array A[X] = Y

Here is my code:

from fractions import gcd
local_gcd=gcd
def F(x):
    global local_gcd
    sum1=0
    for i in range(1,x+1):
         sum1+=local_gcd(i,x)
    return sum1   
size_of_list=int(input())
ele=input()
eles=ele.split(" ")
A=[]
for i in eles:
    A.append(int(i))

num_of_commands=int(input())
mod_val=1000000007
for i in range(0,num_of_commands):
    com=input()
    com_list=com.split(" ")
    x=int(com_list[1])
    y=int(com_list[2])
    sum1=0
    if com_list[0]=='C':
        for i in range(x,y+1):
            sum1+=F(A[i-1])
        print(sum1%mod_val)
    elif com_list[0]=='U':
        A[x-1]=y

Answer 1

You can speed it up using Memoization. That is, once you figure out what F(i) is, you never need to calculate it again.

In your example, the F() invocations you will make are:

F(3), F(4)
F(3), F(4), F(3)
F(3)
F(4), F(4), F(3)
F(4), F(4)

By "memoizing" F(), you only need to compute two values: F(3) and F(4).

If you are using Python 3.2 or later, try the built-in functools.lru_cache decorator which does this automatically: https://stackoverflow.com/a/14731729/4323