給定一個Array，並且給定一個L、R、Value，我們要在陣列的Array[L]跟Array[R]之間加上value。

定義:
前綴和序列:Si=S(i-1)+ai
差分序列:di=ai-ai-1

第一步
建立 Difference Array，長度會比原本的陣列長度再次多一格，DA 中第零個元素等於原陣列的第零個元素，而其他每一個元素的數值都是自己的數值減去前一個數值。

第二步
根據區段做加減，公式為如下 (為何公式這樣定義，後續說明)
DiffArray[L] = DiffArray[L]+value
DiffArray[R] = DiffArray[R+1]-value

第三步
利用 Prefix Sum Array 取得原始陣列

範例:

def initializeDiffArray( A):
    n = len(A)
 
    # We use one extra space because
    # update(l, r, x) updates D[r+1]
    D = [0 for i in range(0 , n + 1)]
 
    D[0] = A[0]; D[n] = 0
     
    for i in range(1, n ):
        D[i] = A[i] - A[i - 1]
    return D
 
 
# Does range update
def update(D, l, r, x):
 
    D[l] += x
    D[r + 1] -= x
 
 
# Prints updated Array
def printArray(A, D):
 
    for i in range(0 , len(A)):
        if (i == 0):
            A[i] = D[i]
 
        # Note that A[0] or D[0] decides
        # values of rest of the elements.
        else:
            A[i] = D[i] + A[i - 1]
 
        print(A[i], end = " ")
     
    print ("")
 
 
# Driver Code
A = [ 10, 5, 20, 40 ]
 
# Create and fill difference Array
D = initializeDiffArray(A)
 
# After below update(l, r, x), the
# elements should become 20, 15, 20, 40
update(D, 0, 1, 10)
printArray(A, D)
 
# After below updates, the
# array should become 30, 35, 70, 60
update(D, 1, 3, 20)
update(D, 2, 2, 30)
printArray(A, D)
 
# This code is contributed by Gitanjali.

資料來源:
https://www.geeksforgeeks.org/difference-array-range-update-query-o1/
https://bythetech.com/blog/article/%E5%B7%AE%E5%88%86-difference-array
https://www.youtube.com/watch?v=l44A2ZIVW40&t=406s