在Python中定义支持范围求和的数据结构的程序

假设我们想要开发一个数据结构，可以使用整数列表进行构建，并且有一个函数可以以有效的方式在需要时查找从索引i到索引j-1的元素的总和。有两个函数。

• 用整数数组构造新实例的构造函数。
• get_sum（i，j）返回数组元素的整数之和，从起始索引i和结束索引j-1开始。

因此，如果输入为array = [5,2,3,6,4,7,8,9,3,2]，则构造一个对象obj，并调用函数obj.get_sum（1,5）和obj.get_sum（4,8），则输出分别为15和28。由于第一个范围元素是[2,3,6,4]，因此总和为15，第二个范围元素是[4,7,8,9]，这里总和为28。

为了解决这个问题，我们将遵循以下步骤−

• 定义构造函数，这将获取数组。
• sums ：=这是一个列表，最初插入0。
• 对于数组中的每个x，执行以下操作
  • 在sums的末尾插入（x +（sums的最后一个项目））。
• 定义一个函数get_sum ()。这将获取i，j。
• 返回sums [j] – sums [i]。

示例

让我们看一下以下实现，以获得更好的理解−

class RangeSum:
    def __init__(self, array):
        self.sums = [0]
        for x in array:
            self.sums.append(x + self.sums[-1])
    def get_sum(self, i, j):
        return self.sums[j] - self.sums[i]

array = [5,2,3,6,4,7,8,9,3,2]
obj = RangeSum(array)
print(obj.get_sum(1,5))
print(obj.get_sum(4,8))

输入

[5,2,3,6,4,7,8,9,3,2]
obj.get_sum(1,5)
obj.get_sum(4,8)

输出

15
28