alexander pantyukhin date november 3 2022 implement the class of prefix sum with useful functions based on it the function returns the sum of array from the start to the end indexes runtime o1 space o1 prefixsum1 2 3 getsum0 2 6 prefixsum1 2 3 getsum1 2 5 prefixsum1 2 3 getsum2 2 3 prefixsum1 2 3 getsum2 3 traceback most recent call last indexerror list index out of range the function returns true if array contains the targetsum false otherwise runtime on space on prefixsum1 2 3 containssum6 true prefixsum1 2 3 containssum5 true prefixsum1 2 3 containssum3 true prefixsum1 2 3 containssum4 false prefixsum1 2 3 containssum7 false prefixsum1 2 3 containssum2 true 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 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
class PrefixSum:
    def __init__(self, array: list[int]) -> None:
        len_array = len(array)
        self.prefix_sum = [0] * len_array

        if len_array > 0:
            self.prefix_sum[0] = array[0]

        for i in range(1, len_array):
            self.prefix_sum[i] = self.prefix_sum[i - 1] + array[i]

    def get_sum(self, start: int, end: int) -> int:
        
        if start == 0:
            return self.prefix_sum[end]

        return self.prefix_sum[end] - self.prefix_sum[start - 1]

    def contains_sum(self, target_sum: int) -> bool:
        

        sums = {0}
        for sum_item in self.prefix_sum:
            if sum_item - target_sum in sums:
                return True

            sums.add(sum_item)

        return False


if __name__ == "__main__":
    import doctest

    doctest.testmod()