data_structures.arrays.prefix_sum

Author : Alexander Pantyukhin Date : November 3, 2022

Implement the class of prefix sum with useful functions based on it.

Classes

PrefixSum

Module Contents

class data_structures.arrays.prefix_sum.PrefixSum(array: list[int])

contains_sum(target_sum: int) → bool

The function returns True if array contains the target_sum, False otherwise.

Runtime : O(n) Space: O(n)

>>> PrefixSum([1,2,3]).contains_sum(6)
True
>>> PrefixSum([1,2,3]).contains_sum(5)
True
>>> PrefixSum([1,2,3]).contains_sum(3)
True
>>> PrefixSum([1,2,3]).contains_sum(4)
False
>>> PrefixSum([1,2,3]).contains_sum(7)
False
>>> PrefixSum([1,-2,3]).contains_sum(2)
True

get_sum(start: int, end: int) → int

The function returns the sum of array from the start to the end indexes. Runtime : O(1) Space: O(1)

>>> PrefixSum([1,2,3]).get_sum(0, 2)
6
>>> PrefixSum([1,2,3]).get_sum(1, 2)
5
>>> PrefixSum([1,2,3]).get_sum(2, 2)
3
>>> PrefixSum([1,2,3]).get_sum(2, 3)
Traceback (most recent call last):
...
IndexError: list index out of range

prefix_sum