【python刷题】差分数组

class Difference:
    def __init__(self, nums):
        self.nums = nums
        self.diff = self.make_diff(self.nums)

    def make_diff(self, nums):
        diff = [0 for _ in range(len(nums))]
        diff[0] = nums[0]
        for i in range(1,len(nums)):
            diff[i] = nums[i] - nums[i-1]
        return diff

    # 给闭区间[i,j]增加val
    # 原理很简单，回想diff数组反推nums数组的过程，diff[i] += 3意味着给nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3，那综合起来，是不是就是对nums[i..j]中的所有元素都加 3 了？
    def increment(self, i, j, val):
        self.diff[i] += val
        if j + 1 < len(self.diff):
            self.diff[j + 1] -= val

    def recover(self):
        rdiff = [0 for _ in range(len(self.diff))]
        rdiff[0] = self.diff[0]
        for i in range(1,len(self.nums)):
            rdiff[i] = rdiff[i-1] + self.diff[i]
        return rdiff



difference = Difference([8,5,9,6,1])
print(difference.diff)
rdiff = difference.recover()
print(rdiff)
difference.increment(2,3,1)
print(difference.diff)
rdiff = difference.recover()
print(rdiff)