How to add a element into array from location L to R?-CodePudding

Suppose I have an array A of size N and want to perform Q queries and each query is the type - "X L R" where X is an element that I want to add in array A from location L to R.

Mathematical format like-

N=5
A=[1 4 3 2 4]
Q=2
X L R=[[5 1 2],
       [-5 1 3]]

my algorithm for this problem is like this-

#python code
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
L=[list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
   for j in range(L[i][1]-1,L[i][2]):
        A[j]=A[j] L[i][0]

but my code takes a long time hence I want to reduce the time of this code.

How I can reduce the time of this code anyone has any idea please let me know. Thank you.

CodePudding user response：

What you basically need is a difference array. That would allow you to get Q update queries done in O(1) time each, plus O(N) complexity to recreate the original array.

CodePudding user response：

n = 5
a = [1, 4, 3, 2, 4]
q = 2
xlr = [[5, 1, 2], [-5, 1, 3]]

for item in xlr:
    # create the list to be inserted first
    to_add = [item[0]]*(item[2]-item[1])
    a[item[1]:item[1]] = to_add
    
print(a)

Inside the for loop, I first create the list that needs to be inserted at the desired location. After that, I set the list that needs to be inserted at the position identified by the element xlr[i][1].

Generated output - [1, -5, -5, 5, 4, 3, 2, 4]