Incrementing elements of particular interval by 1 in fastest way

Question

I have a list of elements represented as array. For the given interval(l,r) '1' should be added to those elements.

 for( i=l;i<=r;i++)
     A[i]++;

It works fine. But I am doing a program to find sum of factorials of large numbers. Since factorial algorithm takes some higher time complexity , I need to reduce the time complexity of the above step which one is required beforehand doing factorial.

Answer 1

You can reduce the time-complexity by incrementing the Array values of 2 elements at a time.

I think the below code will reduce the time-Complexity from O(n) to O(n/2).

for(i=l; i<=r; i++)
{
if(i!=r)
A[r]++;
A[i]++;
r--;
}

Explanation:

Increment the array elements value from both starting index and ending index.

When both index are same the index points to middle element. So we increment only one element (middle element).