Summalista

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, joka laskee tehokkaasti listan osalistan lukujen summan.

Toteuta tiedostoon sumlist.py luokka SumList, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• sum(a, b): laske osalistan lukujen summa kohdasta a kohtaan b

Kummankin metodin tulee toimia ajassa O(1).

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

Listan sisältö on aluksi [1,2,3,4,5], jolloin osalistojen summat ovat seuraavat:

• [1,2,3,4,5]: summa 15
• [2]: summa 2
• [2,3,4]: summa 9
• [3,4]: summa 7
• [1,2,3,4]: summa 10

Sitten listan loppuun lisätään luku 1 ja listan sisällöksi tulee [1,2,3,4,5,1]. Nyt osalistojen summat ovat:

• [1,2,3,4,5,1]: summa 16
• [1]: summa 1

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

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