Cumulative Sum and Difference

04 Feb 2024 in Study / Computer science on Cumulative sum and difference

Algorithm

• Cumulative Sum (누적합)
  • ex. [1, 2, 3] → cumulative sum : [1, 3 (1 + 2), 6 (1 + 2 + 3)]
• Difference (계차)
  • L[i] - L[i-1]
  • assume 0 index : first element of original list
  • ex. [2, 8, 10, 12, 16] → difference : [2, 6 (8 - 2), 2 (10 - 8), 2 (12 - 10), 4 (16 - 12)]
• The relationship between cumulative sum and difference
  • If A list → B list by cumulative sum’s procedure, A list is differece list of B list
  • If A list → B list by differece’s procedure, A list is cumulative sum list of B list

Cumulative Sum

• If we calculate the cumulative sum list’s element from the start to the last, the number of calculations is 1 + 2 + 3 + … + N = N(N + 1)/2 → O(N²) : slow
• If we use difference, O(N)
  • Assume difference list : A, cumulative sum list : B
  • A_i = B_i - B_i-1 → B_i = A_i + B_i-1
  • It is like Dynamic Programming

l = [1, 2, 3]
res = [0] * 3
res[0] = l[0]

for i in range(1, len(l)):
    res[i] = res[i - 1] + l[i]

print(res)

[1, 3, 6]

Difference

• Assume difference list : A, cumulative sum list : B
• A_i = B_i - B_i-1
• O(N)

l = [2, 8, 10, 12, 16]
res = [0] * 5
res[0] = l[0]

for i in range(1, len(l)):
    res[i] = l[i] - l[i - 1]

print(res)

[2, 6, 2, 2, 4]

Example of Cumulative Sum

This is the private repository where I can only review my notes
Repository

Example of Difference

This is the private repository where I can only review my notes
Repository