CSES - Sum list

Your task is to implement a class that maintains a list of numbers and has a method that efficiently computes the sum of the numbers in a given sublist.

In a file sumlist.py, implement the class SumList with the following methods:

  • append(number): add number to the end of the list
  • sum(a, b): return the sum of the numbers from the position a to the position b

Both methods should work in O(1)O(1) time.

class SumList:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def sum(self, a, b):
        # TODO

if __name__ == "__main__":
    numbers = SumList()

    numbers.append(1)
    numbers.append(2)
    numbers.append(3)
    numbers.append(4)
    numbers.append(5)

    print(numbers.sum(0, 4)) # 15
    print(numbers.sum(1, 1)) # 2
    print(numbers.sum(1, 3)) # 9
    print(numbers.sum(2, 3)) # 7
    print(numbers.sum(0, 3)) # 10

    numbers.append(1)
    print(numbers.sum(0, 5)) # 16
    print(numbers.sum(5, 5)) # 1

Here the list content is first set to [1,2,3,4,5][1,2,3,4,5] and then the following sublist sums are computed:

  • [1,2,3,4,5][1,2,3,4,5]: sum 1515
  • [2][2]: sum 22
  • [2,3,4][2,3,4]: sum 99
  • [3,4][3,4]: sum 77
  • [1,2,3,4][1,2,3,4]: sum 1010

Then the number 11 is added to the end of the list and the following sublist sums are computed:

  • [1,2,3,4,5,1][1,2,3,4,5,1]: sum 1616
  • [1][1]: sum 11

You can test the efficiency of your solution with the following code. In this case too the code should finish almost immediately.

    numbers = SumList()
    total = 0
    for i in range(10**5):
        numbers.append(i + 1)
        total += numbers.sum(i // 2, i)
    print(total) # 125005000050000